# zbMATH — the first resource for mathematics

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.

##### MSC:
 05C25 Graphs and abstract algebra (groups, rings, fields, etc.) 20B25 Finite automorphism groups of algebraic, geometric, or combinatorial structures
##### Keywords:
vertex-transitive graphs; Cayley graph