On the number of automorphisms of a regular graph

Wormald, Nicholas

doi:10.1090/S0002-9939-1979-0537102-4

On the number of automorphisms of a regular graph
HTML articles powered by AMS MathViewer

by Nicholas Wormald PDF

Proc. Amer. Math. Soc. 76 (1979), 345-348 Request permission

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

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 460171, DOI 10.1002/jgt.3190010207
L. Babai and L. Lovász, Permutation groups and almost regular graphs, Studia Sci. Math. Hungar. 8 (1973), 141–150. MR 354436
Robert Frucht, Graphs of degree three with a given abstract group, Canad. J. Math. 1 (1949), 365–378. MR 32987, DOI 10.4153/cjm-1949-033-6
Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London 1969. MR 0256911

The number of ways to label a structure

32

Nicholas Wormald, Enumeration of labelled graphs. I. $3$-connected graphs, J. London Math. Soc. (2) 19 (1979), no. 1, 7–12. MR 527727, DOI 10.1112/jlms/s2-19.1.7