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

Properties

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

  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. Dalfó, Cristina, Miguel Angel Fiol, and Ernest Garriga. "On k-Walk-Regular Graphs." the electronic journal of combinatorics (2009): R47-R47.
  3. Camara, Marc, et al. "Geometric aspects of 2-walk-regular graphs." Linear Algebra and its Applications 439.9 (2013): 2692-2710.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.