16-vertex graphs with automorphism groups A4 and A5 from the icosahedron
Abstract
The article deals with the problem of finding vertex-minimal graphs with a given automorphism group. We exhibit two undirected 16-vertex graphs having automorphism groups A4 and A5. It improves Babai's bound for A4 and the graphical regular representation bound for A5. The graphs are constructed using projectivisation of the vertex-face graph of the icosahedron.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2020.8.2.1
References
L. Babai, On the minimum order of graphs with given group, Canad. Math. Bull. 17 (1974), 467--470.
L. Babai, Automorphism groups, isomorphism, reconstruction, In Graham, Ronald L.; Grotschel, Martin; Lovasz, Laszlo, Handbook of Combinatorics I, North-Holland (1995), 1447--1540.
M. Conder, Complete list of all connected edge-transitive bipartite graphs on up to 63 vertices, retrieved February 13, 2019, from https://www.math.auckland.ac.nz/~conder/AllSmallETBgraphs-upto63-full.txt.
P. Daugulis, A note on another construction of graphs with 4n + 6 vertices and cyclic automorphism group of order 4n, Archivum Mathematicum 53 (1) (2017), 13--18.
R. Diestel, Graph Theory. Graduate Texts in Mathematics, Vol.173 (2010), Springer-Verlag, Heidelberg.
M. Liebeck, On graphs whose full automorphism group is an alternating group or a finite classical group, Proc. London Math. Soc. (3) 47 (1983), 337--362.
P. McMullen and E. Schulte, 6C. Projective Regular Polytopes. Abstract Regular Polytopes (1st ed.) Cambridge University Press (2002), pp. 162-165, ISBN 0-521-81496-0.
M.E. Watkins, Graphical regular representations of alternating, symmetric, and miscellaneous small groups, Aequationes mathematicae, 11 (1) (1974), 40--50.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.