Vertices in a graph with the same number of closed walks

Question

A graph is called walk regular if the number of closed walks starting from vertex $u$ of length $k$ does not depend on $u$. If $A$ is the adjacency matrix of the graph, this means that $A^k$ has equal diagonal values for every $k>0$.

I'm interested in a weaker condition, that there exists two vertices $u,v$ such that the number of closed walks of length $k$ is the same for $u$ and $v$. Are there results or references about this?

In other words, when does $[A^k]_{uu} = [A^k]_{vv}$ hold?

---

For example, it would be nice to have necessary/sufficient conditions for this property to hold. If there is a graph automorphism that maps $u\to v$ then certainly $u$ and $v$ have the same number of closed walks, though the existence of such an automorphism is not necessary (an example is the Folkman graph which is walk-regular but not vertex-transitive).

I'm aware that if the graph has $n$ vertices and $u,v$ have the same number of closed walks for $k=1,2,\ldots n-1$, then by Hamilton-Cayley's theorem it is true also for all $k\geq n$.

I'm asking in the case of a simple undirected graph, but if there are generalizations for directed and/or weighted graphs they're highly welcome.

Answer 1

Continuing my search through various articles, I found the answer: two such vertices are called cospectral vertices.

There is a result, that for an undirected graph $G$ with adjacency matrix $A$, the following are equivalent to $u,v$ cospectral:

1. For every integer $k>0$, $[A^k]_{u,u}=[A^k]_{v,v}$.
2. The graphs obtained removing a vertex, $G\setminus \{u\}$ and $G\setminus \{v\}$ have the same spectrum
3. For every $\lambda$ eigenvalue of $A$, let $P$ be the spectral projector on the $\lambda$-Eigenspace of $A$ (since $A$ is symmetric, $P$ is orthogonal). The condition is then $P_{u,u} = P_{v,v}$ for every spectral projector.

Equivalently, the third condition can be reformulated through graph angles.

---

References:

Chris Godsil, Jamie Smith, "Strongly Cospectral Vertices" , on arXiv https://arxiv.org/abs/1709.07975
In this articles more equivalent conditions are given, and is studied a generalization of the concept.

Chris Godsil, Brendan D. McKay, "Feasibility Conditions for the existence of Walk-Regular Graphs" , Linear Algebra Appl., Vol. 30 (1980), pp. 51-61
This paper proves properties for walk-regular graphs, but its results can be applied also to cospectral vertices.

Dragoš Cvetković, Peter Rowlinson, Slobodan Simić, "Eigenspaces of Graphs", Cambridge University Press (1997)
A very good book, where can be found results concerning graph angles.

Allen J. Schwenk,"Almost all trees are cospectral" , New Directions in the Theory of Graphs, Academic Press (1973), pp. 275–307
I think this was the first paper to use cospectral vertices (although as in the above condition 2, so not explicitly).