Walk-regular graph

This article needs additional citations for verification. Please help by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources:  –  ·  ·  · scholar · JSTOR (October 2019) (Learn how and when to remove this template message)

This article possibly contains original research. Please by verifying the claims made and adding inline citations. Statements consisting only of original research should be removed. (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 ${\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 – 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.

References[]

External links[]

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