Small vertex‐transitive and Cayley graphs of girth six and given degree: an algebraic approach |
| |
| Authors: | Eyal Loz Martin Mačaj Mirka Miller Jana Šiagiová Jozef Širáň Jana Tomanová |
| |
| Affiliation: | 1. University of auckland auckland, New Zealand;2. Comenius university bratislava, Slovakia;3. The university of newcastle newcastle, Australia;4. University of west bohemia pilsen, Czech Republic;5. Kings college, London, United Kingdom;6. Itb bandung, Indonesia;7. Slovak university of technology bratislava, Slovakia;8. Open university, Milton Keynes, United Kingdom |
| |
| Abstract: | 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 |
| |
| Keywords: | graph girth degree cage |
|
|
