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
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 $ \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?)

  • [1] R. Frucht, Herstellung von Graphen mit vorgegebener abstrakter Gruppe, Compositio Math. 6 (1938), 239-250. MR 1557026
  • [2] -, On the groups of repeated graphs, Bull. Amer. Math. Soc. 55 (1949), 418-420. MR 10, 615. MR 0029492 (10:615a)
  • [3] R. Frucht, A. Gewirtz and L. 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 Math., vol. 186, Springer-Verlag, Berlin and New York, 1971, pp. 95-104. MR 43 #6119. MR 0280399 (43:6119)
  • [4] A. Gewirtz, A. Hill and L. V. Quintas, Extremum problems concerning graphs and their groups, Combinatorial Structures and Their Applications (Proc. Calgary Internat. Conf. Combinatorial Structures and Their Applications, Calgary, Alberta, 1969), Gordon and Breach, New York, 1970, pp. 103-109. MR 42 #108. MR 0265196 (42:108)
  • [5] G. Haggard, The least number of edges for graphs having dihedral automorphism group, Discrete Math. 6 (1973), 53-78. MR 48 #157. MR 0321790 (48:157)
  • [6] M. Hall, Jr., The theory of groups, Macmillan, New York, 1959. MR 21 #1996. MR 0103215 (21:1996)
  • [7] F. Harary, Graph theory, Addison-Wesley, Reading, Mass., 1969. MR 41 #1566. MR 0256911 (41:1566)
  • [8] F. Harary and G. Prins, The number of homeomorphically irreducible trees, and other species, Acta Math. 101 (1959), 141-162. MR 21 #653. MR 0101846 (21:653)
  • [9] A. Kerbet, Representations of permutation groups. I, Lecture Notes in Math., vol. 240, Springer-Verlag, Berlin and New York, 1971. MR 0325752 (48:4098)
  • [10] B. H. Neumann, Lectures on topics in the theory of infinite groups, Tata Institute of Fundamental Research, Bombay, 1960. MR 0266979 (42:1881)
  • [11] O. Ore, The theory of graphs, Amer. Math. Soc. Colloq. Publ., vol. 38, Amer. Math. Soc., Providence, R. I., 1962. MR 27 #740. MR 0150753 (27:740)
  • [12] -, Theory of monomial groups, Trans. Amer. Math. Soc. 51 (1942), 15-64. MR 3, 197. MR 0005739 (3:197e)
  • [13] L. V. Quintas, Extrema concerning asymmetric graphs, J. Combinatorial Theory 3 (1967), 57-82. MR 35 #2780. MR 0211905 (35:2780)
  • [14] -, The least number of edges for graphs having symmetric automorphism group, J. Combinatorial Theory 5 (1968), 115-125. MR 37 #6211. MR 0230651 (37:6211)
  • [15] P. K. Stockmeyer, The enumeration of groups with prescribed automorphism group, Ph. D. Dissertation, University of Michigan, Ann Arbor, Mich., 1971.
  • [16] G. Haggard, D. McCarthy and A. Wohlgemuth, Extremal edge problems for graphs with given hyperoctahedral automorphism group (to appear). MR 0453585 (56:11847)

Similar Articles

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

American Mathematical Society