Isomorphism Problem for Relational Structures with a Cyclic Automorphism

The problem we discuss here is the conjecture of Ádám [1] concerning the isomorphism problem of cyclic (or, in other words, circulant) graphs and its generalization by Babai [4]. We attempt to give a fairly complete survey of results related to Ádám's conjecture. We prove that the isomorphism classes of all n-element relational structures (not only graphs) with cyclic automorphism have the anticipated simple form if and only if (n, ϕ(n)) = 1 or n = 4, where ϕ(n) is Euler's ϕ function. The same result holds if only quaternary relational structures are considered