| Abstract: | The Petersen graph on 10 vertices is the smallest example of a vertex-transitive graph that is not a Cayley graph. In 1983, D. Marus˘ic˘ asked, “For what values of n does there exist such a graph on n vertices?” We give several new constructions of families of vertex-transitive graphs that are not Cayley graphs and complete the proof that, if n is divisible by p2 for some prime p, then there is a vertex-transitive graph on n vertices that is not a Cayley graph unless n is p2, p3, or 12. © 1996 John Wiley & Sons, Inc. |
