Automorphism Groups in Extremal Families of Polyhedral Graphs

We study automorphism groups in five extremal families of polyhedral graphs.

For every $n\ge14$, we prove that every minimum-order $3$-polytopal graph containing a vertex of each degree $3,4,\ldots,n$ is asymmetric.

The proof uses an exact planar defect decomposition, a complete description of the high-degree tail, and a saturation theorem for the subgraph induced by the uniquely high-degree vertices.

Duality gives the corresponding asymmetry result for minimum-face polyhedra containing faces of every size $3,4,\ldots,n$.

For the three polyhedral graphs whose complements are also polyhedral, we determine the ordinary and extended automorphism groups and identify the extended group \[ \mathsf{Aut}^{\pm}(G_{13})\cong (C_2\times C_2)\rtimes C_4. \] Next, we classify automorphism groups of radius-one polyhedra.

In the unique-dominating-vertex case they are cyclic or dihedral, and in the triangulated case the possibilities are \[ 1,\qquad C_2,\qquad C_3,\qquad C_2\times C_2,\qquad S_3. \] For polyhedra that are unigraphic among the class of self-dual, we show that their automorphism group is either $1$ or $C_2$.

Finally, we consider polyhedra that are products of graphs, for each of the four standard graph products, and we classify them according to their automorphism group.