Walk-regular graph
 | This article needs additional citations for verification. (October 2019) (Learn how and when to remove this template message) |
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 [math]\displaystyle{ G }[/math] is a simple graph. Let [math]\displaystyle{ A }[/math] denote the adjacency matrix of [math]\displaystyle{ G }[/math], [math]\displaystyle{ V(G) }[/math] denote the set of vertices of [math]\displaystyle{ G }[/math], and [math]\displaystyle{ \Phi_{G - v}(x) }[/math] denote the characteristic polynomial of the vertex-deleted subgraph [math]\displaystyle{ G - v }[/math] for all [math]\displaystyle{ v \in V(G). }[/math]Then the following are equivalent:
- [math]\displaystyle{ G }[/math] is walk-regular.
- [math]\displaystyle{ A^k }[/math] is a constant-diagonal matrix for all [math]\displaystyle{ k \geq 0. }[/math]
- [math]\displaystyle{ \Phi_{G - u}(x) = \Phi_{G - v}(x) }[/math] for all [math]\displaystyle{ u, v \in V(G). }[/math]
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.
[math]\displaystyle{ k }[/math]-walk-regular graphs
A graph is [math]\displaystyle{ k }[/math]-walk regular if for any two vertices [math]\displaystyle{ v }[/math] and [math]\displaystyle{ w }[/math] of graph-distance [math]\displaystyle{ \mathrm{dist}(v,w)\le k }[/math] the number of walks of length [math]\displaystyle{ \ell }[/math] from [math]\displaystyle{ v }[/math] to [math]\displaystyle{ w }[/math] depends only of [math]\displaystyle{ k }[/math] and [math]\displaystyle{ \ell }[/math]. [2]
For [math]\displaystyle{ k=0 }[/math] these are exactly the walk-regular graphs.
If [math]\displaystyle{ k }[/math] is at least the diameter of the graph, then the [math]\displaystyle{ k }[/math]-walk regular graphs coincide with the distance-regular graphs. In fact, if [math]\displaystyle{ k\ge 2 }[/math] and the graph has an eigenvalue of multiplicity at most [math]\displaystyle{ k }[/math] (except for eigenvalues [math]\displaystyle{ d }[/math] and [math]\displaystyle{ -d }[/math], where [math]\displaystyle{ d }[/math] is the degree of the graph), then the graph is already distance-regular. [3]
References
- ↑ "Are there only finitely many distinct cubic walk-regular graphs that are neither vertex-transitive nor distance-regular?". https://mathoverflow.net/a/264155.
- ↑ Dalfó, Cristina, Miguel Angel Fiol, and Ernest Garriga. "On k-Walk-Regular Graphs." the electronic journal of combinatorics (2009): R47-R47.
- ↑ Camara, Marc, 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.
 |  |
