Walk-regular graph

In discrete mathematics, a walk-regular graph is a simple graph where the number of closed walks of any length from a vertex to itself does not depend on the choice of vertex.

Equivalent definitions

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

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

Examples

• The vertex-transitive graphs are walk-regular.
• The semi-symmetric 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.
  • It is triangle-free and has at most five distinct eigenvalues.
  • It is bipartite and has at most six distinct eigenvalues.

Properties

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

$k$-walk-regular graphs

A graph is $k$-walk regular if for any two vertices $v$ and $w$ of graph-distance $\mathrm {dist} (v,w)\leq k$ the number of walks of length $\ell$ from $v$ to $w$ depends only of $k$ and $\ell$.

For $k=0$ these are exactly the walk-regular graphs.

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

External links

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