Vertex-transitive graphs which are not Cayley graphs. I. (English) Zbl 0795.05070

There are vertex-transitive graphs which are not Cayley graphs, e.g. the Petersen graph. The present paper considers the problem of determining orders of such graphs. If (a) \(k=m^ 4\), \(m \geq 2\); (b) \(k=p^ 2q\), \(p,q\) prime, \(p \geq 2\), \(q \geq 3\), \(p \neq q\), \(q\) is not dividing \(p^ 2-1\); (c) \(k=2m\), \(m \geq 7\), \(m\) is not the product of distinct primes of the form \(4t +3\), or (d) \(k=n^ 2m^ 2\), \(k \geq 2\), \(m \geq 2\), then there is a vertex-transitive graph of order \(k\) which is not a Cayley graph. The proof is given by construction.


05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
20B25 Finite automorphism groups of algebraic, geometric, or combinatorial structures