Non-isomorphic Cayley Graphs with Identical Random Walk Distribution
The Electronic Journal of Combinatorics · 2026-07-03 · 33 (3)
DOI: 10.37236/14208 ↗At a glance
Journal article in The Electronic Journal of Combinatorics, published online on 2026-07-03. Written by Masao Ishikawa and 2 co-authors.
Abstract (original language)
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. The two Cayley graphs $Cay(G, S_1)$ and $Cay(G, S_2)$ are non-isomorphic. 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. 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.
Cite
APA
Ishikawa, M., Nakano, F., & Sadahiro, T. (2026). Non-isomorphic Cayley Graphs with Identical Random Walk Distribution. The Electronic Journal of Combinatorics, 33(3). https://doi.org/10.37236/14208
Vancouver
Ishikawa M, Nakano F, Sadahiro T. Non-isomorphic Cayley Graphs with Identical Random Walk Distribution. The Electronic Journal of Combinatorics. 2026;33(3). doi:10.37236/14208
BibTeX
@article{Ishikawa2026,
author = {Ishikawa, Masao and Nakano, Fumihiko and Sadahiro, Taizo},
title = {Non-isomorphic Cayley Graphs with Identical Random Walk Distribution},
journal = {The Electronic Journal of Combinatorics},
year = {2026},
volume = {33},
number = {3},
doi = {10.37236/14208}
}
EUVIMED