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
has
distinct nonzero eigenvalues, Khan and Haidar (2026, Theorem A) prove that walk-regularity
is equivalent to constant diagonals for all of
where
is the Moore-Penrose matrix inverse.
In this case every power of
has constant diagonal. Requiring just the first power to
have constant diagonal defines the weaker class of resistance-regular
graphs.