walk-regular graph

In graph theory, a walk-regular graph is a simple graph where the number of closed walks of any length $\ell$ from a vertex to itself does only depend on $\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.

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

Examples

The vertex-transitive graphs are walk-regular.
The semi-symmetric graphs are walk-regular.{{Cite web|url=https://mathoverflow.net/a/264155|title=Are there only finitely many distinct cubic walk-regular graphs that are neither vertex-transitive nor distance-regular?|website=mathoverflow.net|access-date=2017-07-21}}{{Unreliable source?|date=July 2017|sure=yes}}
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|date=October 2019}}{{citation needed|date=October 2019}}
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 $\ell$ from $v$ to $w$ depends only on $k$ and $\ell$ .

Cristina Dalfó, Miguel Angel Fiol, and Ernest Garriga, "On $k$ -Walk-Regular Graphs," Electronic Journal of Combinatorics 16(1) (2009), article R47.

For $k=0$ these are exactly the 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 $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.Marc Camara et al., "Geometric aspects of 2-walk-regular graphs," Linear Algebra and its Applications 439(9) (2013), 2692-2710.

References

External links

Chris Godsil and Brendan McKay, [http://www.sciencedirect.com/science/article/pii/0024379580901809 Feasibility conditions for the existence of walk-regular graphs].

Category:Algebraic graph theory

Category:Graph families

Category:Regular graphs