Walk-regular graph explained

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} (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} (x) = \Phi _{G} (x) for all u, v \in V(G).

Examples

• The vertex-transitive graphs are walk-regular.
• The semi-symmetric graphs are walk-regular.^[1]
• 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 distance at most k, the number of walks of length l from v to w depends only on k and l .^[2]

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

External links

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

Notes and References

1. Web site: Are there only finitely many distinct cubic walk-regular graphs that are neither vertex-transitive nor distance-regular?. mathoverflow.net. 2017-07-21.
2. Cristina Dalfó, Miguel Angel Fiol, and Ernest Garriga, "On 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.