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

Authors:
E. Seah and D. R. Stinson

Journal:
Math. Comp. **50** (1988), 607-618

MSC:
Primary 05C30; Secondary 05B30, 05C45, 05C70, 20B25

DOI:
https://doi.org/10.1090/S0025-5718-1988-0929557-1

MathSciNet review:
929557

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 , excluding those one-factorizations containing exactly one automorphism of six disjoint cycles of length two, there are precisely 56391 nonisomorphic one-factorizations of with nontrivial automorphism groups. We also determined that there are precisely 21 perfect one-factorizations of that have nontrivial automorphism groups.

**[1]**P. J. Cameron, "Minimal edge-colourings of complete grahs,"*J. London Math. Soc.*(2), v. 11, 1975, pp. 337-346. MR**0422088 (54:10080)****[2]**P. J. Cameron,*Parallelisms of Complete Designs*, London Math. Soc. Lecture Note Ser., vol. 23, Cambridge Univ. Press, Cambridge, 1976. MR**0419245 (54:7269)****[3]**L. E. Dickson & F. H. Safford, "Solution to problem 8 (group theory),"*Amer Math. Monthly*, v. 13, 1906, pp. 150-151. MR**1516644****[4]**E. N. Gelling,*On*1-*factorizations of the Complete Graph and the Relationship to Round Robin Schedules*, M.A. Thesis, University of Victoria, 1973.**[5]**F. Harary,*Graph Theory*, Addison-Wesley, Reading, Mass., 1969. MR**0256911 (41:1566)****[6]**E. Ihrig, "Symmetry groups related to the construction of perfect one-factorizations of ,"*J. Combin. Theory Ser. B*, v.40, 1986, pp. 121-151. MR**838214 (87i:05107)****[7]**E. Ihrig, "The structure of the symmetry groups of perfect one-factorizations of ." (To appear.)**[8]**W. L. Kocay, D. R. Stinson & S. A. Vanstone, "On strong starters in cyclic groups,"*Discrete Math.*, v. 56, 1985, pp. 45-60. MR**808085 (87a:05045)****[9]**C. C. Lindner, E. Mendelsohn & A. Rosa, "On the number of 1-factorizations of the complete graph,"*J. Combin. Theory*, v. 20, 1976, pp. 265-282. MR**0491359 (58:10617)****[10]**E. Mendelsohn & A. Rosa, "One-factorizations of the complete graph--A survey,"*J. Graph Theory*, v. 9, 1985, pp. 43-65. MR**785649 (86h:05089)****[11]**K. T. Phelps & S. A. Vanstone, "Isomorphism of strong starters in cyclic groups." (Preprint.) MR**1111563 (92c:05030)****[12]**R. C. Read, "Every one a winner,"*Ann. Discrete Math.*, v. 2, 1978, pp. 107-120. MR**0491273 (58:10537)****[13]**E. Seah & D. R. Stinson, "An enumeration of non-isomorphic one-factorizations and Howell designs for the graph minus a one-factor,"*Ars Combin.*, v. 21, 1986, pp. 145-161. MR**846688 (87i:05159)****[14]**E. Seah & D. R. Stinson, "Some perfect one-factorizations of ,"*Ann. Discrete Math.*(To appear.) MR**949778 (89e:05161)****[15]**W. D. Wallis, A. P. Street & J. S. Wallis,*Combinatorics*:*Room Squares, Sum-Free Sets, Hadamard Matrices*, Lecture Notes in Math., vol. 292, Springer-Verlag, New York, 1972. MR**0392580 (52:13397)****[16]**W. D. Wallis, "On one-factorizations of complete graphs,"*J. Austral. Math. Soc.*, v. 16, 1973, pp. 167-171. MR**0329972 (48:8311)**

Retrieve articles in *Mathematics of Computation*
with MSC:
05C30,
05B30,
05C45,
05C70,
20B25

Retrieve articles in all journals with MSC: 05C30, 05B30, 05C45, 05C70, 20B25

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1988-0929557-1

Article copyright:
© Copyright 1988
American Mathematical Society