Walk-regular graph

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 $G$ is a simple graph. Let $A$ denote the adjacency matrix of $G$, $V(G)$ denote the set of vertices of $G$, and $\Phi _{G-v}(x)$ denote the characteristic polynomial of the vertex-deleted subgraph $G-v$ for all $v\in V(G).$Then the following are equivalent:

• $G$ is walk-regular.
• $A^{k}$ is a constant-diagonal matrix for all $k\geq 0$.
• $\Phi _{G-u}(x)=\Phi _{G-v}(x)$ for all $u,v\in V(G)$.