Non-isomorphic walk-regular graphs with the same number of closed walks at any length

Question

Are there known examples of couples of non-isomorphic walk-regular graphs with adjacency matrix $A_1$ and $A_2$ and such that $(A_1^k)_{i,i} = (A_2^k)_{i,i}$ for all $k \gt 0$?

Answer 1

You are asking for two non-isomorphic cospectral walk-regular graphs, presumably not vertex-transitive.

The following two are examples. They are bipartite and 4-regular on 18 vertices. Both of them have characteristic polynomial $$ (x+4) (x+2)^4 (x+1)^4 (x-1)^4 (x-2)^4 (x-4).$$

0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1
0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1
0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0
0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0
0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0
1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0
1 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0
1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0
1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0
0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0
0 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0
0 0 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1
0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1
0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 1
0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0
0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0
1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0
1 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0
1 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0
0 1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0

In case graph6 format is useful for you, it is

Q??????pcXSWcWWgHK?{?LO@w??
Q??????pciPSgWTGHW@X?Ko@w??

I had these on my computer for at least 10 years but I don't know if they are published anywhere.