On solvable groups and circulant graphs

Let phi be Euler's phi function. We prove that a vertex-transitive graph Gamma of order n, with gcd(n, phi(n)) = 1, is isomorphic to a circulant graph of order n if and only if Aut(Gamma) contains a transitive solvable subgroup. As a corollary, we prove that every vertex-transitive graph Gamma of order n is isomorphic to a circulant graph of order n if and only if for every such Gamma, Aut(Gamma) contains a transitive solvable subgroup and n = 4, 6, or gcd(n, phi(n)) = 1. (C) 2000 Academic Press.