Premium
Vertex‐transitive graphs that are not Cayley graphs. II
Author(s) -
McKay Brendan D.,
Praeger Cheryl E.
Publication year - 1996
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199608)22:4<321::aid-jgt6>3.0.co;2-n
Subject(s) - combinatorics , vertex transitive graph , cayley graph , mathematics , symmetric graph , petersen graph , discrete mathematics , vertex (graph theory) , transitive relation , graph , voltage graph , line graph
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 p 2 for some prime p , then there is a vertex‐transitive graph on n vertices that is not a Cayley graph unless n is p 2 , p 3 , or 12. © 1996 John Wiley & Sons, Inc.