Walk-regular graph

In graph theory, a walk-regular graph is a simple graph where the number of closed walks of any length

from a vertex to itself does only depend on

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.

is a simple graph.

denote the adjacency matrix of

denote the set of vertices of

denote the characteristic polynomial of the vertex-deleted subgraph

Then the following are equivalent: A graph is

the number of walks of length

these are exactly the walk-regular graphs.

In analogy to walk-regular graphs generalizing vertex-transitive graphs, 1-walk-regular graphs can be thought of as generalizing symmetric graphs, that is, graphs that are both vertex- and edge-transitive.

For example, the Hoffman graph is 1-walk-regular but not symmetric.

is at least the diameter of the graph, then the

-walk-regular graphs coincide with the distance-regular graphs.

and the graph has an eigenvalue of multiplicity at most

is the degree of the graph), then the graph is already distance-regular.