On the enumeration of onefactorizations of complete graphs containing prescribed automorphism groups
Authors:
E. Seah and D. R. Stinson
Journal:
Math. Comp. 50 (1988), 607618
MSC:
Primary 05C30; Secondary 05B30, 05C45, 05C70, 20B25
MathSciNet review:
929557
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: In this paper we use orderly algorithms to enumerate (perfect) onefactorizations of complete graphs, the automorphism groups of which contain certain prescribed subgroups. We showed that, for the complete graph , excluding those onefactorizations containing exactly one automorphism of six disjoint cycles of length two, there are precisely 56391 nonisomorphic onefactorizations of with nontrivial automorphism groups. We also determined that there are precisely 21 perfect onefactorizations of that have nontrivial automorphism groups.
 [1]
Peter
J. Cameron, Minimal edgecolourings of complete graphs, J.
London Math. Soc. (2) 11 (1975), no. 3,
337–346. MR 0422088
(54 #10080)
 [2]
Peter
J. Cameron, Parallelisms of complete designs, Cambridge
University Press, CambridgeNew YorkMelbourne, 1976. London Mathematical
Society Lecture Note Series, No. 23. MR 0419245
(54 #7269)
 [3]
L.
E. Dickson and F.
H. Safford, Solutions of Problems: Group Theory: 8, Amer.
Math. Monthly 13 (1906), no. 67, 150–151. MR
1516644, http://dx.doi.org/10.2307/2970423
 [4]
E. N. Gelling, On 1factorizations of the Complete Graph and the Relationship to Round Robin Schedules, M.A. Thesis, University of Victoria, 1973.
 [5]
Frank
Harary, Graph theory, AddisonWesley Publishing Co., Reading,
Mass.Menlo Park, Calif.London, 1969. MR 0256911
(41 #1566)
 [6]
Edwin
C. Ihrig, Symmetry groups related to the construction of perfect
onefactorizations of 𝐾_{2𝑛}, J. Combin. Theory Ser. B
40 (1986), no. 2, 121–151. MR 838214
(87i:05107), http://dx.doi.org/10.1016/00958956(86)900729
 [7]
E. Ihrig, "The structure of the symmetry groups of perfect onefactorizations 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
(87a:05045), http://dx.doi.org/10.1016/0012365X(85)901918
 [9]
Charles
C. Lindner, Eric
Mendelsohn, and Alexander
Rosa, On the number of 1factorizations of the complete graph,
J. Combinatorial Theory Ser. B 20 (1976), no. 3,
265–282. MR 0491359
(58 #10617)
 [10]
Eric
Mendelsohn and Alexander
Rosa, Onefactorizations of the complete graph—a survey,
J. Graph Theory 9 (1985), no. 1, 43–65. MR 785649
(86h:05089), http://dx.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
(92c:05030), http://dx.doi.org/10.1016/00973165(91)90051H
 [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
(58 #10537)
 [13]
E.
Seah and D.
R. Stinson, An enumeration of nonisomorphic onefactorizations and
Howell designs for the graph 𝐾₁₀ minus a
onefactor, Ars Combin. 21 (1986), 145–161. MR 846688
(87i:05159)
 [14]
E.
Seah and D.
R. Stinson, A perfect onefactorization for
𝐾₃₆, Discrete Math. 70 (1988),
no. 2, 199–202. MR 949778
(89e:05161), http://dx.doi.org/10.1016/0012365X(88)900933
 [15]
W.
D. Wallis, Anne
Penfold Street, and Jennifer
Seberry Wallis, Combinatorics: Room squares, sumfree sets,
Hadamard matrices, Lecture Notes in Mathematics, Vol. 292,
SpringerVerlag, BerlinNew York, 1972. MR 0392580
(52 #13397)
 [16]
W.
D. Wallis, On onefactorizations of complete graphs, J.
Austral. Math. Soc. 16 (1973), 167–171. Collection
of articles dedicated to the memory of Hanna Neumann, II. MR 0329972
(48 #8311)
 [1]
 P. J. Cameron, "Minimal edgecolourings of complete grahs," J. London Math. Soc. (2), v. 11, 1975, pp. 337346. 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. 150151. MR 1516644
 [4]
 E. N. Gelling, On 1factorizations of the Complete Graph and the Relationship to Round Robin Schedules, M.A. Thesis, University of Victoria, 1973.
 [5]
 F. Harary, Graph Theory, AddisonWesley, Reading, Mass., 1969. MR 0256911 (41:1566)
 [6]
 E. Ihrig, "Symmetry groups related to the construction of perfect onefactorizations of ," J. Combin. Theory Ser. B, v.40, 1986, pp. 121151. MR 838214 (87i:05107)
 [7]
 E. Ihrig, "The structure of the symmetry groups of perfect onefactorizations 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. 4560. MR 808085 (87a:05045)
 [9]
 C. C. Lindner, E. Mendelsohn & A. Rosa, "On the number of 1factorizations of the complete graph," J. Combin. Theory, v. 20, 1976, pp. 265282. MR 0491359 (58:10617)
 [10]
 E. Mendelsohn & A. Rosa, "Onefactorizations of the complete graphA survey," J. Graph Theory, v. 9, 1985, pp. 4365. 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. 107120. MR 0491273 (58:10537)
 [13]
 E. Seah & D. R. Stinson, "An enumeration of nonisomorphic onefactorizations and Howell designs for the graph minus a onefactor," Ars Combin., v. 21, 1986, pp. 145161. MR 846688 (87i:05159)
 [14]
 E. Seah & D. R. Stinson, "Some perfect onefactorizations of ," Ann. Discrete Math. (To appear.) MR 949778 (89e:05161)
 [15]
 W. D. Wallis, A. P. Street & J. S. Wallis, Combinatorics: Room Squares, SumFree Sets, Hadamard Matrices, Lecture Notes in Math., vol. 292, SpringerVerlag, New York, 1972. MR 0392580 (52:13397)
 [16]
 W. D. Wallis, "On onefactorizations of complete graphs," J. Austral. Math. Soc., v. 16, 1973, pp. 167171. 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
DOI:
http://dx.doi.org/10.1090/S00255718198809295571
PII:
S 00255718(1988)09295571
Article copyright:
© Copyright 1988
American Mathematical Society
