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

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]**Peter J. Cameron,*Minimal edge-colourings of complete graphs*, J. London Math. Soc. (2)**11**(1975), no. 3, 337–346. MR**0422088**, https://doi.org/10.1112/jlms/s2-11.3.337**[2]**Peter J. Cameron,*Parallelisms of complete designs*, Cambridge University Press, Cambridge-New York-Melbourne, 1976. London Mathematical Society Lecture Note Series, No. 23. MR**0419245****[3]**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**, https://doi.org/10.2307/2970423**[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]**Frank Harary,*Graph theory*, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London, 1969. MR**0256911****[6]**Edwin C. Ihrig,*Symmetry groups related to the construction of perfect one-factorizations of 𝐾_{2𝑛}*, J. Combin. Theory Ser. B**40**(1986), no. 2, 121–151. MR**838214**, https://doi.org/10.1016/0095-8956(86)90072-9**[7]**E. Ihrig, "The structure of the symmetry groups of perfect one-factorizations of ." (To appear.)**[8]**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**, https://doi.org/10.1016/0012-365X(85)90191-8**[9]**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**0491359****[10]**Eric Mendelsohn and Alexander Rosa,*One-factorizations of the complete graph—a survey*, J. Graph Theory**9**(1985), no. 1, 43–65. MR**785649**, https://doi.org/10.1002/jgt.3190090104**[11]**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**, https://doi.org/10.1016/0097-3165(91)90051-H**[12]**Ronald C. Read,*Every one a winner or how to avoid isomorphism search when cataloguing combinatorial configurations*, Ann. Discrete Math.**2**(1978), 107–120. Algorithmic aspects of combinatorics (Conf., Vancouver Island, B.C., 1976). MR**0491273****[13]**E. Seah and D. R. Stinson,*An enumeration of nonisomorphic one-factorizations and Howell designs for the graph 𝐾₁₀ minus a one-factor*, Ars Combin.**21**(1986), 145–161. MR**846688****[14]**E. Seah and D. R. Stinson,*A perfect one-factorization for 𝐾₃₆*, Discrete Math.**70**(1988), no. 2, 199–202. MR**949778**, https://doi.org/10.1016/0012-365X(88)90093-3**[15]**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****[16]**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**

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