Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



On the number of automorphisms of a regular graph

Author: Nicholas Wormald
Journal: Proc. Amer. Math. Soc. 76 (1979), 345-348
MSC: Primary 05C25
MathSciNet review: 537102
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: For any connected cubic graph G with 2n points, the number of automorphisms of G divides $ 3n{2^n}$. This is a special case of a result which is proved for connected regular graphs in general. The result is shown to be best possible for infinitely many n in the cubic case.

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

  • [1] L. Babai, Some applications of graph contractions, J. Graph Theory 1 (1977), 125-130. MR 0460171 (57:167)
  • [2] L. Babai and L. Lovasz, Permutation groups and almost regular graphs, Studia Sci. Math. Hungar. 8 (1973), 141-150. MR 0354436 (50:6914)
  • [3] R. Frucht, Graphs of degree three with a given abstract group, Canad. J. Math. 1 (1949), 365-378. MR 0032987 (11:377c)
  • [4] F. Harary, Graph theory, Addison-Wesley, Reading, Mass., 1969. MR 0256911 (41:1566)
  • [5] F. Harary, E. M. Palmer and R. C. Read, The number of ways to label a structure, Psychometrika 32 (1967), 155-156.
  • [6] N. Wormald, Enumeration of labelled graphs II: Cubic graphs with a given connectivity, J. London Math. Soc. (to appear). MR 545196 (80i:05052b)

Similar Articles

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

Retrieve articles in all journals with MSC: 05C25

Additional Information

Article copyright: © Copyright 1979 American Mathematical Society

American Mathematical Society