A Stability Theorem for Minimum Edge Graphs with Given Abstract Automorphism Group
Donald J. McCarthy, Louis V. Quintas · Transactions of the American Mathematical Society · 1975
Given a finite abstract group $\mathcal {G}$, whenever $n$ is sufficiently large there exist graphs with $n$ vertices and automorphism group isomorphic to $\mathcal {G}$. Let $(\mathcal {G},n)$ denote the minimum number of edges possible in such a graph. It is shown that for each $\mathcal {G}$ there always exists a graph $M$ such that for $n$ sufficiently large, $e(\mathcal {G},n)$ is attained by adding to $M$ a standard maximal component asymmetric forest. A characterization of the graph $M$ is given, a formula for $e(\mathcal {G},n)$ is obtained (for large $n$), and the minimum edge problem is re-examined in the light of these results.