Walk-regular graph
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.
≈ 1 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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. \Phi_{G - u}(x) = \Phi_{G - v}(x) for all u, v \in V(G).
Text derived from https://en.wikipedia.org/w/index.php?oldid=1330034833 under CC BY-SA 4.0; modifications have been made.