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)

This article possibly contains original research. Please improve it 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 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. 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.

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

• The vertex-transitive graphs are walk-regular.
• The semi-symmetric graphs are walk-regular.^{[citation needed]}
• 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.

• 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.
• Complements of walk-regular graphs are walk-regular. ^[1]
• Cartesian products of walk-regular graphs are walk-regular.^[1]
• Categorical products of walk-regular graphs are walk-regular.^[1]
• Strong products of walk-regular graphs are walk-regular. ^[1]
• In general, the line graph of a walk-regular graph is not walk-regular.

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

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

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