Walk-regular graph

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

References

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.