Toida's conjecture

Both conjectures concern circulant graphs. These are graphs defined from a positive integer ${\displaystyle n}$ and a set ${\displaystyle S}$ of positive integers. Their vertices can be identified with the numbers from 0 to ${\displaystyle n-1}$, and two vertices ${\displaystyle i}$ and ${\displaystyle j}$ are connected by an edge whenever their difference modulo ${\displaystyle n}$ belongs to set ${\displaystyle S}$. Every symmetry of the cyclic group of addition modulo ${\displaystyle n}$ gives rise to a symmetry of the ${\displaystyle n}$-vertex circulant graphs, and Ádám conjectured (incorrectly) that these are the only symmetries of the circulant graphs.

However, the known counterexamples to Ádám's conjecture involve sets ${\displaystyle S}$ in which some elements share non-trivial divisors with ${\displaystyle n}$. Toida's conjecture states that, when every member of ${\displaystyle S}$ is relatively prime to ${\displaystyle n}$, then the only symmetries of the circulant graph for ${\displaystyle n}$ and ${\displaystyle S}$ are symmetries coming from the underlying cyclic group.

The conjecture was proven in the special case where n is a prime power by Klin and Poschel in 1978,[2] and by Golfand, Najmark, and Poschel in 1984.[3]

The conjecture was then fully proven by Muzychuk, Klin, and Poschel in 2001 by using Schur algebra,[4] and simultaneously by Dobson and Morris in 2002 by using the classification of finite simple groups.[5]