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ászló Babai, Some applications of graph contractions, J. Graph Theory 1 (1977), no. 2, 125–130. Special issue dedicated to Paul Turán. MR 0460171
  • [2] L. Babai and L. Lovász, Permutation groups and almost regular graphs, Studia Sci. Math. Hungar. 8 (1973), 141–150. MR 0354436
  • [3] Robert Frucht, Graphs of degree three with a given abstract group, Canadian J. Math. 1 (1949), 365–378. MR 0032987
  • [4] Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London, 1969. MR 0256911
  • [5] F. Harary, E. M. Palmer and R. C. Read, The number of ways to label a structure, Psychometrika 32 (1967), 155-156.
  • [6] Nicholas C. Wormald, Enumeration of labelled graphs. II. Cubic graphs with a given connectivity, J. London Math. Soc. (2) 20 (1979), no. 1, 1–7. MR 545196, 10.1112/jlms/s2-20.1.1

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