This article needs additional citations for
verification. (October 2019) |
![]() | This article possibly contains
original research. (October 2019) |
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.
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:
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]
This article needs additional citations for
verification. (October 2019) |
![]() | This article possibly contains
original research. (October 2019) |
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.
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:
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]