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 is a simple graph. Let denote the adjacency matrix of , denote the set of vertices of , and denote the characteristic polynomial of the vertex-deleted subgraph for all Then the following are equivalent: is walk-regular. is a constant-diagonal matrix for all for all
Examples
The vertex-transitive graphs are walk-regular. The semi-symmetric graphs are walk-regular. 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.
-walk-regular graphs
A graph is -walk regular if for any two vertices and of graph-distance the number of walks of length from to depends only of and .
For these are exactly the walk-regular graphs.
If is at least the diameter of the graph, then the -walk regular graphs coincide with the distance-regular graphs. In fact, if and the graph has an eigenvalue of multiplicity at most (except for eigenvalues and , where is the degree of the graph), then the graph is already distance-regular.
References
External links
Chris Godsil and Brendan McKay, Feasibility conditions for the existence of walk-regular graphs.