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.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 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.

Sources cited in this revision

2 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.