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.

Equivalent definitions

Suppose that is a simple graph. Let denote the adjacency matrix of, denote the set of vertices of, and denote the characteristic polynomial of the vertex-deleted subgraph for all Then the following are equivalent:

is walk-regular.
is a constant-diagonal matrix for all
for all

Examples

The vertex-transitive graphs are walk-regular.
The distance-regular graphs are walk-regular. More generally, any simple graph in a homogeneous coherent algebra is walk-regular.
A connected regular graph is walk-regular if it has at most four distinct eigenvalues.

Properties

A walk-regular graph is necessarily a regular graph, since the number of closed walks of length two starting at any vertex is twice the vertex's degree.
Complements of walk-regular graphs are walk-regular.
Cartesian products of walk-regular graphs are walk-regular.
Categorical products of walk-regular graphs are walk-regular.
Strong products of walk-regular graphs are walk-regular.
In general, the line graph of a walk-regular graph is not walk-regular.

''k''-walk-regular graphs

A graph is -walk-regular if for any two vertices and of distance at most the number of walks of length from to depends only on and.
The class of -walk-regular graphs is exactly the class of 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.
If is at least the diameter of the graph, then the -walk-regular graphs coincide with the distance-regular graphs.
In fact, if and the graph has an eigenvalue of multiplicity at most, then the graph is already distance-regular.