TOPICS
Search

Walk-Regular Graph


A walk-regular graph is a finite simple graph for which the number of closed walks of each length starting at a vertex is independent of that vertex (Godsil and McKay 1980). Equivalently, every nonnegative integer power of its adjacency matrix has constant diagonal. Every walk-regular graph is regular, since the number of closed walks of length 2 is the vertex degree. Every vertex-transitive graph is walk-regular.

For a connected graph whose Laplacian matrix L has m distinct nonzero eigenvalues, Khan and Haidar (2026, Theorem A) prove that walk-regularity is equivalent to constant diagonals for all of

 L^|,(L^|)^2,...,(L^|)^(m-1),

where L^| is the Moore-Penrose matrix inverse. In this case every power of L^| has constant diagonal. Requiring just the first power to have constant diagonal defines the weaker class of resistance-regular graphs.


See also

Adjacency Matrix, Regular Graph, Resistance-Regular Graph, Vertex-Transitive Graph

Explore with Wolfram|Alpha

References

Godsil, C. D. and McKay, B. D. "Feasibility Conditions for the Existence of Walk-Regular Graphs." Lin. Alg. Appl. 30, 51-61, 1980.Khan, M. ul I. and Haidar, G. "Resistance-Regular Graphs Need Not Be Regular." 12 Nov 2026. https://arxiv.org/abs/2611.21670v1.

Cite this as:

Weisstein, Eric W. "Walk-Regular Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Walk-RegularGraph.html

Subject classifications