Walk-regular graph

In graph theory, a walk-regular graph is a simple graph where the number of closed walks of any length ℓ {\displaystyle \ell } from a vertex to itself does only depend on ℓ {\displaystyle \ell } but not depend on the choice of vertex.^[1] 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.

Suppose that G {\displaystyle G} is a simple graph. Let A {\displaystyle A} denote the adjacency matrix of G {\displaystyle G} , V ( G ) {\displaystyle V(G)} denote the set of vertices of G {\displaystyle G} , and Φ G − v ( x ) {\displaystyle \Phi _{G-v}(x)} denote the characteristic polynomial of the vertex-deleted subgraph G − v {\displaystyle G-v} for all v ∈ V ( G ) . {\displaystyle v\in V(G).} Then the following are equivalent:

• G {\displaystyle G} is walk-regular.
• A k {\displaystyle A^{k}} is a constant-diagonal matrix for all k ≥ 0. {\displaystyle k\geq 0.}
• Φ G − u ( x ) = Φ G − v ( x ) {\displaystyle \Phi _{G-u}(x)=\Phi _{G-v}(x)} for all u , v ∈ V ( G ) . {\displaystyle u,v\in V(G).}

• The vertex-transitive graphs are walk-regular.^[2]
• The distance-regular graphs are walk-regular.^[1] 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.^[2]

• 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.^[1]
• Complements of walk-regular graphs are walk-regular. ^[3]
• Cartesian products of walk-regular graphs are walk-regular.^[3]
• Categorical products of walk-regular graphs are walk-regular.^[3]
• Strong products of walk-regular graphs are walk-regular. ^[3]
• In general, the line graph of a walk-regular graph is not walk-regular.

A graph is k {\displaystyle k} -walk-regular if for any two vertices v {\displaystyle v} and w {\displaystyle w} of distance at most k , {\displaystyle k,} the number of walks of length ℓ {\displaystyle \ell } from v {\displaystyle v} to w {\displaystyle w} depends only on k {\displaystyle k} and ℓ {\displaystyle \ell } .^[1][4]

The class of 0 {\displaystyle 0} -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 k {\displaystyle k} is at least the diameter of the graph, then the k {\displaystyle k} -walk-regular graphs coincide with the distance-regular graphs. In fact, if k ≥ 2 {\displaystyle k\geq 2} and the graph has an eigenvalue of multiplicity at most k {\displaystyle k} (except for eigenvalues d {\displaystyle d} and − d {\displaystyle -d} , where d {\displaystyle d} is the degree of the graph), then the graph is already distance-regular.^[5]