Jump to content

Walk-regular graph

From Wikipedia, the free encyclopedia

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

[edit]

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

[edit]

Properties

[edit]

k-walk-regular graphs

[edit]

A graph is -walk regular if for any two vertices and of distance at most the number of walks of length from to depends only on and . [2]

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

References

[edit]
  1. ^ "Are there only finitely many distinct cubic walk-regular graphs that are neither vertex-transitive nor distance-regular?". mathoverflow.net. Retrieved 2017-07-21.
  2. ^ Cristina Dalfó, Miguel Angel Fiol, and Ernest Garriga, "On -Walk-Regular Graphs," Electronic Journal of Combinatorics 16(1) (2009), article R47.
  3. ^ Marc Camara et al., "Geometric aspects of 2-walk-regular graphs," Linear Algebra and its Applications 439(9) (2013), 2692-2710.
[edit]