Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



A stability theorem for minimum edge graphs with given abstract automorphism group

Authors: Donald J. McCarthy and Louis V. Quintas
Journal: Trans. Amer. Math. Soc. 208 (1975), 27-39
MSC: Primary 05C25
MathSciNet review: 0369148
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: 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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05C25

Retrieve articles in all journals with MSC: 05C25

Additional Information

Keywords: Automorphism groups of graphs, minimum edge problem
Article copyright: © Copyright 1975 American Mathematical Society

American Mathematical Society