Non-isomorphic Cayley Graphs with Identical Random Walk Distribution
The Electronic Journal of Combinatorics · 03.07.2026 · 33 (3)
DOI: 10.37236/14208 ↗Kurz gefasst
Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 03.07.2026. Verfasst von Masao Ishikawa und 2 weiteren Autor:innen.
Abstract (Originalsprache)
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.
Zitieren
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