Let $G=(V,E)$ be an undirected graph. A walk of length $k$ in $G$ is a sequence of vertices $v_1,v_2,\ldots,v_{k+1}$ in $V$ such that $(v_i,v_{i+1})\in E$ for each $i=1,2,\ldots,k$.
Call two graphs $G=(V,E)$ and $H=(W,F)$ $k$-walk-equivalent if $G$ and $H$ have the same number of walks of length at most $k$. Two graphs are walk-equivalent if they are $k$-walk equivalent for any $k$. Note that walks do not have to be closed, i.e., the begin and end vertex of a walk may be different.
Suppose that $G$ and $H$ have the same number $n$ of vertices. Let $A_G$ and $A_H$ denote the $n\times n$ adjacency matrices of $G$ and $H$, respectively. It is known (or least is implicit in Theorem 3 in [1]) that
Theorem 1 Two graphs $G$ and $H$ are walk-equivalent if and only if there exists a real matrix $S$ such that $A_H\cdot X=X\cdot A_G$, $S\cdot\mathbf{1}=\mathbf{1}$, and $S^t\cdot\mathbf{1}=\mathbf{1}$.
Here $\mathbf{1}$ denotes the $n\times 1$-vector consisting of all ones; $S^t$ denotes the transposed matrix of $S$.
Question: Is there a similar characterization for $k$-walk-equivalent graphs?
Alternatively, walk-equivalence can be phrased in terms of spectral properties of $G$ and $H$.
Theorem 2 Two graphs $G$ and $H$ are walk-equivalent if and only if they have the same main eigenvalues and main angles.
Here, an eigenvalue $\lambda$ is main if its eigenspace is not orthogonal to $\mathbf{1}$. Furthermore, the main angle of $\lambda$ is the cosine of the angle between its eigenspace and $\mathbf{1}$. (Hence, the main angle of a main eigenvalue is larger than 0.) See e.g., [2] or [3].
Question Is there a characterization of $k$-walk-equivalent graphs in terms of their spectral properties?
This question pops up in a setting where graphs can only be explored locally in $k$-bounded neighborhoods and as a result one is not able to perform walks of arbitrary lengths.
1 Erwin R. van Dam, Willem H. Haemers, and Jack H. Koolen. Cospectral graphs and the generalized adjacency matrix. Linear Algebra and its Applications, 423(1):33 – 41, 2007. https://doi.org/10.1016/j.laa.2006.07.017
2 Frank Harary and Allen J. Schwenk. The spectral approach to determining the number of walks in a graph. Pacific J. Math., 80(2):443–449, 1979. https://projecteuclid.org:443/euclid.pjm/1102785717.
3 Dragoˇs M. Cvetkovi ́c. The main part of the spectrum, divisors and switching of graphs. Publ. Inst. Math. (Beograd) (N.S.), 23(37):31–38, 1978. http://elib.mi.sanu.ac.rs/files/journals/publ/43/6.pdf.
