On the enumeration of one-factorizations of complete graphs containing prescribed automorphism groups

Seah, E.; Stinson, D. R.

doi:10.1090/S0025-5718-1988-0929557-1

On the enumeration of one-factorizations of complete graphs containing prescribed automorphism groups
HTML articles powered by AMS MathViewer

by E. Seah and D. R. Stinson PDF

Math. Comp. 50 (1988), 607-618 Request permission

Abstract:

In this paper we use orderly algorithms to enumerate (perfect) one-factorizations of complete graphs, the automorphism groups of which contain certain prescribed subgroups. We showed that, for the complete graph ${K_{12}}$, excluding those one-factorizations containing exactly one automorphism of six disjoint cycles of length two, there are precisely 56391 nonisomorphic one-factorizations of ${K_{12}}$ with nontrivial automorphism groups. We also determined that there are precisely 21 perfect one-factorizations of ${K_{14}}$ that have nontrivial automorphism groups.

References

Peter J. Cameron, Minimal edge-colourings of complete graphs, J. London Math. Soc. (2) 11 (1975), no. 3, 337–346. MR 422088, DOI 10.1112/jlms/s2-11.3.337
Peter J. Cameron, Parallelisms of complete designs, London Mathematical Society Lecture Note Series, No. 23, Cambridge University Press, Cambridge-New York-Melbourne, 1976. MR 0419245
L. E. Dickson and F. H. Safford, Solutions of Problems: Group Theory: 8, Amer. Math. Monthly 13 (1906), no. 6-7, 150–151. MR 1516644, DOI 10.2307/2970423

On

factorizations of the Complete Graph and the Relationship to Round Robin Schedules

Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London 1969. MR 0256911
Edwin C. Ihrig, Symmetry groups related to the construction of perfect one-factorizations of $K_{2n}$, J. Combin. Theory Ser. B 40 (1986), no. 2, 121–151. MR 838214, DOI 10.1016/0095-8956(86)90072-9
W. L. Kocay, D. R. Stinson, and S. A. Vanstone, On strong starters in cyclic groups, Discrete Math. 56 (1985), no. 1, 45–60. MR 808085, DOI 10.1016/0012-365X(85)90191-8
Charles C. Lindner, Eric Mendelsohn, and Alexander Rosa, On the number of $1$-factorizations of the complete graph, J. Combinatorial Theory Ser. B 20 (1976), no. 3, 265–282. MR 491359, DOI 10.1016/0095-8956(76)90017-4
Eric Mendelsohn and Alexander Rosa, One-factorizations of the complete graph—a survey, J. Graph Theory 9 (1985), no. 1, 43–65. MR 785649, DOI 10.1002/jgt.3190090104
K. T. Phelps and S. A. Vanstone, Isomorphism of strong starters in cyclic groups, J. Combin. Theory Ser. A 57 (1991), no. 2, 287–293. MR 1111563, DOI 10.1016/0097-3165(91)90051-H
Ronald C. Read, Every one a winner or how to avoid isomorphism search when cataloguing combinatorial configurations, Ann. Discrete Math. 2 (1978), 107–120. MR 491273
E. Seah and D. R. Stinson, An enumeration of nonisomorphic one-factorizations and Howell designs for the graph $K_{10}$ minus a one-factor, Ars Combin. 21 (1986), 145–161. MR 846688
E. Seah and D. R. Stinson, A perfect one-factorization for $K_{36}$, Discrete Math. 70 (1988), no. 2, 199–202. MR 949778, DOI 10.1016/0012-365X(88)90093-3
W. D. Wallis, Anne Penfold Street, and Jennifer Seberry Wallis, Combinatorics: Room squares, sum-free sets, Hadamard matrices, Lecture Notes in Mathematics, Vol. 292, Springer-Verlag, Berlin-New York, 1972. MR 0392580
W. D. Wallis, On one-factorizations of complete graphs, J. Austral. Math. Soc. 16 (1973), 167–171. Collection of articles dedicated to the memory of Hanna Neumann, II. MR 0329972