Toida's conjecture is true

Edward Dobson ; Joy Morris

The electronic journal of combinatorics, Tome 9 (2002)

Résumé

Let $S$ be a subset of the units in ${\bf Z_n}$. Let ${\Gamma}$ be a circulant graph of order $n$ (a Cayley graph of ${\bf Z_n}$) such that if $ij\in E({\Gamma})$, then $i - j$ (mod $n$) $\in S$. Toida conjectured that if $\Gamma'$ is another circulant graph of order $n$, then ${\Gamma}$ and ${\Gamma '}$ are isomorphic if and only if they are isomorphic by a group automorphism of ${\bf Z_n}$ In this paper, we prove that Toida's conjecture is true. We further prove that Toida's conjecture implies Zibin's conjecture, a generalization of Toida's conjecture.

Détail

DOI : 10.37236/1651

Classification : 05C25, 20B25
Mots-clés : Cayley graph, circulant graph, group automorphism, Zibin's conjecture