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

McCarthy, Donald J.; Quintas, Louis V.

doi:10.1090/S0002-9947-1975-0369148-4

A stability theorem for minimum edge graphs with given abstract automorphism group
HTML articles powered by AMS MathViewer

by Donald J. McCarthy and Louis V. Quintas PDF

Trans. Amer. Math. Soc. 208 (1975), 27-39 Request permission

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

R. Frucht, Herstellung von Graphen mit vorgegebener abstrakter Gruppe, Compositio Math. 6 (1939), 239–250 (German). MR 1557026
Robert Frucht, On the groups of repeated graphs, Bull. Amer. Math. Soc. 55 (1949), 418–420. MR 29492, DOI 10.1090/S0002-9904-1949-09230-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
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
Gary Haggard, The least number of edges for graphs having dihedral automorphism group, Discrete Math. 6 (1973), 53–78. MR 321790, DOI 10.1016/0012-365X(73)90036-8
Marshall Hall Jr., The theory of groups, The Macmillan Company, New York, N.Y., 1959. MR 0103215
Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London 1969. MR 0256911, DOI 10.21236/AD0705364
Frank Harary and Geert Prins, The number of homeomorphically irreducible trees, and other species, Acta Math. 101 (1959), 141–162. MR 101846, DOI 10.1007/BF02559543
Adalbert Kerber, Representations of permutation groups. I, Lecture Notes in Mathematics, Vol. 240, Springer-Verlag, Berlin-New York, 1971. MR 0325752, DOI 10.1007/BFb0067943
B. H. Neumann, Lectures on topics in the theory of infinite groups, Tata Institute of Fundamental Research Lectures on Mathematics, No. 21, Tata Institute of Fundamental Research, Bombay, 1968. Notes by M. Pavman Murthy. MR 0266979
Oystein Ore, Theory of graphs, American Mathematical Society Colloquium Publications, Vol. XXXVIII, American Mathematical Society, Providence, R.I., 1962. MR 0150753
Oystein Ore, Theory of monomial groups, Trans. Amer. Math. Soc. 51 (1942), 15–64. MR 5739, DOI 10.1090/S0002-9947-1942-0005739-6
Louis V. Quintas, Extrema concerning asymmetric graphs, J. Combinatorial Theory 3 (1967), 57–82. MR 211905, DOI 10.1016/S0021-9800(67)80018-8
Louis V. Quintas, The least number of edges for graphs having symmetric automorphism group, J. Combinatorial Theory 5 (1968), 115–125. MR 230651, DOI 10.1016/S0021-9800(68)80046-8

The enumeration of groups with prescribed automorphism group

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 453585, DOI 10.1016/0012-365X(76)90057-1