KAIST Discrete Math Seminar

Walk-regular graph were introduced by Godsil and McKay to understand when the characteristic polynomial of a graph in which a vertex is deleted does not depend on which vertex you delete. This notion was generalized to m-walk-regular graphs by Fiol and Garriga in order to understand how close you can come to a distance-regular graph.

We observed that for many results on distance-regular graphs they also hold for 2-walk-regular. In this talk I will give an overview of which results can be generalized to 2-walk-regular graphs, and I also will give many examples of 2,3,4,5,-walk-regular graphs which are not distance-regular. At this moment all 6-walk-regular graphs known are distance-regular.

This is still work in progress and is joint work with M. Camara, E. van Dam and Jongyook Park.