Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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
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 $ {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 [Enhancements On Off] (What's this?)

  • [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 $ {K_{2n}}$," 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 $ {K_{2n}}$." (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 $ {K_{10}}$ 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 $ {K_{14}}$," 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)

Similar Articles

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

Article copyright: © Copyright 1988 American Mathematical Society

American Mathematical Society