Premium
Small vertex‐transitive and Cayley graphs of girth six and given degree: an algebraic approach
Author(s) -
Loz Eyal,
Mačaj Martin,
Miller Mirka,
Šiagiová Jana,
Širáň Jozef,
Tomanová Jana
Publication year - 2011
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/jgt.20556
Subject(s) - mathematics , combinatorics , transitive relation , cayley graph , vertex (graph theory) , vertex transitive graph , odd graph , discrete mathematics , quotient , degree (music) , symmetric graph , indifference graph , chordal graph , graph , 1 planar graph , line graph , voltage graph , physics , acoustics
We examine the existing constructions of the smallest known vertex‐transitive graphs of a given degree and girth 6. It turns out that most of these graphs can be described in terms of regular lifts of suitable quotient graphs. A further outcome of our analysis is a precise identification of which of these graphs are Cayley. We also investigate higher level of transitivity of the smallest known vertex‐transitive graphs of a given degree and girth 6 and relate their constructions to near‐difference sets. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:265‐284, 2011