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

DOI:
https://doi.org/10.1090/S0002-9947-1975-0369148-4

MathSciNet review:
0369148

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Given a finite abstract group , whenever is sufficiently large there exist graphs with vertices and automorphism group isomorphic to . Let denote the minimum number of edges possible in such a graph. It is shown that for each there always exists a graph such that for sufficiently large, is attained by adding to a standard maximal component asymmetric forest. A characterization of the graph is given, a formula for is obtained (for large ), and the minimum edge problem is re-examined in the light of these results.

**[1]**R. Frucht,*Herstellung von Graphen mit vorgegebener abstrakter Gruppe*, Compositio Math.**6**(1939), 239–250 (German). MR**1557026****[2]**Robert Frucht,*On the groups of repeated graphs*, Bull. Amer. Math. Soc.**55**(1949), 418–420. MR**0029492**, https://doi.org/10.1090/S0002-9904-1949-09230-3**[3]**Roberto Frucht, Allan Gewirtz, and Louis V. Quintas,*The least number of edges for graphs having automorphism group of order three*, Recent Trends in Graph Theory (Proc. Conf., New York, 1970) Lecture Notes in Mathematics, Vol. 186. Springer, Berlin, 1971, pp. 95–104. MR**0280399****[4]**Allan Gewirtz, Anthony Hill, and Louis V. Quintas,*Extremum problems concerning graphs and their groups*, Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969) Gordon and Breach, New York, 1970, pp. 103–109. MR**0265196****[5]**Gary Haggard,*The least number of edges for graphs having dihedral automorphism group*, Discrete Math.**6**(1973), 53–78. MR**0321790**, https://doi.org/10.1016/0012-365X(73)90036-8**[6]**Marshall Hall Jr.,*The theory of groups*, The Macmillan Co., New York, N.Y., 1959. MR**0103215****[7]**Frank Harary,*Graph theory*, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London, 1969. MR**0256911****[8]**Frank Harary and Geert Prins,*The number of homeomorphically irreducible trees, and other species.*, Acta Math.**101**(1959), 141–162. MR**0101846**, https://doi.org/10.1007/BF02559543**[9]**Adalbert Kerber,*Representations of permutation groups. I*, Lecture Notes in Mathematics, Vol. 240, Springer-Verlag, Berlin-New York, 1971. MR**0325752****[10]**B. H. Neumann,*Lectures on topics in the theory of infinite groups*, Notes by M. Pavman Murthy. Tata Institute of Fundamental Research Lectures on Mathematics, No. 21, Tata Institute of Fundamental Research, Bombay, 1968. MR**0266979****[11]**Oystein Ore,*Theory of graphs*, American Mathematical Society Colloquium Publications, Vol. XXXVIII, American Mathematical Society, Providence, R.I., 1962. MR**0150753****[12]**Oystein Ore,*Theory of monomial groups*, Trans. Amer. Math. Soc.**51**(1942), 15–64. MR**0005739**, https://doi.org/10.1090/S0002-9947-1942-0005739-6**[13]**Louis V. Quintas,*Extrema concerning asymmetric graphs*, J. Combinatorial Theory**3**(1967), 57–82. MR**0211905****[14]**Louis V. Quintas,*The least number of edges for graphs having symmetric automorphism group*, J. Combinatorial Theory**5**(1968), 115–125. MR**0230651****[15]**P. K. Stockmeyer,*The enumeration of groups with prescribed automorphism group*, Ph. D. Dissertation, University of Michigan, Ann Arbor, Mich., 1971.**[16]**Gary Haggard, Donald McCarthy, and Andrew Wohlgemuth,*Extremal edge problems for graphs with given hyperoctahedral automorphism group*, Discrete Math.**14**(1976), no. 2, 139–156. MR**0453585**, https://doi.org/10.1016/0012-365X(76)90057-1

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

Retrieve articles in all journals with MSC: 05C25

Additional Information

DOI:
https://doi.org/10.1090/S0002-9947-1975-0369148-4

Keywords:
Automorphism groups of graphs,
minimum edge problem

Article copyright:
© Copyright 1975
American Mathematical Society