Non-isomorphic Cayley Graphs with Identical Random Walk Distribution

Abstract

We construct an infinite family of triples $(G, S_1, S_2)$ each consisting of a group $G$ and a pair $(S_1, S_2)$ of distinct subsets of $G$ with the following properties.

1.   The two Cayley graphs $Cay(G, S_1)$ and $Cay(G, S_2)$ are non-isomorphic.
2.  The distributions of the simple random walks on $Cay(G, S_1)$ and $Cay(G, S_2)$ are the same if one applies an appropriate bijection between the two vertex sets at each step.
3.  The spectral set of $Cay(G, S_i)$ is decomposed into a disjoint union of two subsets $A$ and $B_i$ of the equal size ($|A|=|B_i|=|G|/2$), which satisfies $B_2=-B_1=\left\{-\lambda\,|\,\lambda\in B_1\right\}$.

As a byproduct, an infinite family of pairs of isomorphic Cayley graphs on non-isomorphic groups is obtained.