This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Walk-regular graph" – news · newspapers · books · scholar · JSTOR (October 2019) (Learn how and when to remove this message)

This article possibly contains original research. Please improve it by verifying the claims made and adding inline citations. Statements consisting only of original research should be removed. (October 2019) (Learn how and when to remove this message)

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. 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 ${\displaystyle G}$ is a simple graph. Let ${\displaystyle A}$ denote the adjacency matrix of ${\displaystyle G}$, ${\displaystyle V(G)}$ denote the set of vertices of ${\displaystyle G}$, and ${\displaystyle \Phi _{G-v}(x)}$ denote the characteristic polynomial of the vertex-deleted subgraph ${\displaystyle G-v}$ for all ${\displaystyle v\in V(G).}$Then the following are equivalent:

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

• The vertex-transitive graphs are walk-regular.
• The semi-symmetric graphs are walk-regular.^{[1][unreliable source]}
• 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:^{[dubious – discuss][citation needed]}
  • It has at most four distinct eigenvalues.
  • It is triangle-free and has at most five distinct eigenvalues.
  • It is bipartite and has at most six distinct eigenvalues.

• A walk-regular graph is necessarily a regular graph.
• 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.

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

For ${\displaystyle k=0}$ 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.

If ${\displaystyle k}$ is at least the diameter of the graph, then the ${\displaystyle k}$-walk-regular graphs coincide with the distance-regular graphs. In fact, if ${\displaystyle k\geq 2}$ and the graph has an eigenvalue of multiplicity at most ${\displaystyle k}$ (except for eigenvalues ${\displaystyle d}$ and ${\displaystyle -d}$, where ${\displaystyle d}$ is the degree of the graph), then the graph is already distance-regular.^[3]

• Chris Godsil and Brendan McKay, Feasibility conditions for the existence of walk-regular graphs.