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 ${\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).}$

Examples

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

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 ${\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 l}$ from ${\displaystyle v}$ to ${\displaystyle w}$ depends only on ${\displaystyle k}$ and ${\displaystyle l}$. ^[2]

For ${\displaystyle k=0}$ these are exactly the walk-regular graphs.

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]

References

1. "Are there only finitely many distinct cubic walk-regular graphs that are neither vertex-transitive nor distance-regular?". mathoverflow.net. Retrieved 2017-07-21.
2. Cristina Dalfó, Miguel Angel Fiol, and Ernest Garriga, "On ${\displaystyle k}$-Walk-Regular Graphs," Electronic Journal of Combinatorics 16(1) (2009), article R47.
3. Marc Camara et al., "Geometric aspects of 2-walk-regular graphs," Linear Algebra and its Applications 439(9) (2013), 2692-2710.

External links

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