Walk-regular graph

Summary

In graph theory, a walk-regular graph is a simple graph where the number of closed walks of any length $\ell$ from a vertex to itself does only depend on $\ell$ but not depend on the choice of vertex. Walk-regular graphs can be thought of as a spectral graph theory analogue of vertex-transitive graphs. While a walk-regular graph is not necessarily very symmetric, all its vertices still behave identically with respect to the graph's spectral properties.