EUVIMEDSkopri EUVIMED
Crossref

Non-isomorphic Cayley Graphs with Identical Random Walk Distribution

Masao Ishikawa, Fumihiko Nakano, Taizo Sadahiro

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.

AstrattDettalji biblijografiċiCiteRelated studies

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}
}
Start for free →