Walk-regular graph

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Walk-regular graph" – news · newspapers · books · scholar · JSTOR (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 – discuss][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

External links

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

0.00 (0 votes) Original source: https://en.wikipedia.org/wiki/Walk-regular graph. Read more