$16$-vertex graphs with automorphism groups $A_4$ and $A_5$ from 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 $A_4$ and $A_5$. It improves the Babai's bound for $A_4$ and the graphical regular representation bound for $A_5$. The graphs are constructed using projectivisation of the vertex-face graph of icosahedron.