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.

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

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.^[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.

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

The class of ${\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 ${\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.^[5]

References

1. Dalfó, C.; Fiol, M.A.; Garriga, E. (2009). "On k-Walk-Regular Graphs". Electronic Journal of Combinatorics. 16 (1): #R47. doi:10.37236/136.
2. Brouwer, Andries E.; Haemers, Willem H. (2012), "Graphs with few eigenvalues", Spectra of Graphs (PDF), Universitext, New York, NY: Springer, pp. 217–218, doi:10.1007/978-1-4614-1939-6, ISBN 978-1-4614-1939-6
3. Godsil, C.D.; McKay, B.D. (April 1980). "Feasibility conditions for the existence of walk-regular graphs". Linear Algebra and Its Applications. 30: 51–61. doi:10.1016/0024-3795(80)90180-9.
4. Dalfó, C.; Fiol, M.A.; Garriga, E. (August 2009). "On t-Cliques in k-Walk-Regular Graphs". Electronic Notes in Discrete Mathematics. 34: 579–584. doi:10.1016/j.endm.2009.07.096. hdl:2117/10784.
5. Cámara, Marc; van Dam, Edwin R.; Koolen, Jack H.; Park, Jongyook (November 2013). "Geometric aspects of 2-walk-regular graphs". Linear Algebra and Its Applications. 439 (9): 2692–2710. arXiv:1304.2905. doi:10.1016/j.laa.2013.07.028.