Frontiers of Mathematics in China >
Almost resolvable maximum packings of complete graphs with 5-cycles
Received date: 08 Nov 2013
Accepted date: 20 Aug 2014
Published date: 12 Feb 2015
Copyright
Let X be the vertex set of KnA k-cycle packing of Kn is a triple (X,C,L), where C is a collection of edge disjoint k-cycles of Kn and L is the collection of edges of Kn not belonging to any of the k-cycles in C. A k-cycle packing (X,C,L) is called resolvable if C can be partitioned into almost parallel classes. A resolvable maximum k-cycle packing of Kn, denoted by k-RMCP(n), is a resolvable k-cycle packing of Kn, (X,C,L), in which the number of almost parallel classes is as large as possible. Let D(n, k) denote the number of almost parallel classes in a k-RMCP(n). D(n, k) for k = 3, 4 has been decided. When n ≡ k (mod 2k) and k ≡ 1 (mod 2) or n ≡ 1 (mod 2k) and k ∈{6, 8, 10, 14}∪{m: 5≤m≤49, m ≡ 1 (mod 2)}, D(n, k) also has been decided with few possible exceptions. In this paper, we shall decide D(n, 5) for all values of n≥5.
Key words： Cycle packing; resolvable maximum cycle packing; cycle frame
Min ZHOU , Haitao CAO . Almost resolvable maximum packings of complete graphs with 5-cycles[J]. Frontiers of Mathematics in China, 2015 , 10(2) : 461 -475 . DOI: 10.1007/s11464-015-0425-7
| 1 |
Abel R J R, Brouwer A E, Colbourn C J, Dinitz J H. Mutually orthogonal Latin squares. In: The CRC Handbook of Combinatorial Designs. 2nd ed. Boca Raton: CRC Press, 2007, 160-193
|
| 2 |
Adams P, Billington E J, Hoffman D G. The generalized almost resolvable cycle system problem. Combinatorica, 2010, 30: 617-625
|
| 3 |
Alspach B, Gavlas H. Cycle decompositions of Kn and Kn - I. J Combin Theory Ser B, 2011, 81: 77-99
|
| 4 |
Alspach B, Schellenberg P J, Stinson D R, Wagner D. The Oberwolfach problem and factors of uniform odd length cycles. J Combin Theory Ser A, 1989, 52: 20-43
|
| 5 |
Assaf B, Hartman A. Resolvable group divisible designs with block size 3. Discrete Math, 1989, 77: 5-20
|
| 6 |
Billington E J, Dejter I J, Hoffman D G, Lindner C C. Almost resolvable maximum packing of complete graphs with 4-cycles. Graphs Combin, 2011, 27: 161-170
|
| 7 |
Billington E J, Hoffman D G, Lindner C C, Meszka M. Almost resolvable minimum coverings of complete graphs with 4-cycles. Australas J Combin, 2011, 50: 73-85
|
| 8 |
Bryant D, Horsley D. Packing cycles in complete graphs. J Combin Theory Ser B, 2008, 98: 1014-1037
|
| 9 |
Bryant D, Rodger C A. Cycle decompositions. In: The CRC Handbook of Combinatorial Designs. 2nd ed. Boca Raton: CRC Press, 2007, 373-382
|
| 10 |
Cao H, Niu M, Tang C. On the existence of cycle frame and almost resolvable cycle systems. Discrete Math, 2011, 311: 2220-2232
|
| 11 |
Colbourn C J, Hoffman D G, Rees R. A new class of group divisible designs with block size three. J Combin Theory Ser A, 1992, 59: 73-89
|
| 12 |
Dejter I J, Linder C C, Meszka M, Rodger C A. Almost resolvable 4-cycle systems. J Combin Math Combin Comput, 2007, 63: 173-182. Corrigendum: ibid, 2008, 66: 297-298
|
| 13 |
El-Zanati S I. Maximum packings with odd cycles. Discrete Math, 1994, 131: 91-97
|
| 14 |
Hoffman D G, Schellenberg P J. The existence of Ck-factorizations of K2n-F.Discrete Math, 1991, 97: 243-250
|
| 15 |
Horsley D. Maximum packings of the complete graph with uniform length cycles. J Graph Theory, 2011, 68: 1-7
|
| 16 |
Kennedy J A. Maximum packings of Kn with hexagons. Australas J Combin, 1993, 7: 101-110. Corrigendum: ibid, 1994, 10: 293
|
| 17 |
Lenz H. Some remarks on pairwise balanced designs. Mitt Math Sem Giessen, 1984, 165: 49-62
|
| 18 |
Lindner C C, Meszka M, Rosa A. Almost resolvable cycle systems—an analogue of Hanani triple system. J Combin Des, 2009, 17(5): 404-410
|
| 19 |
Lindner C C, Rodger C A. Decomposition into cycles II: Cycle systems. In: Contemporary Design Theory: A Collection of Surveys. New York: Wiley, 1992, 325-369
|
| 20 |
Liu J. A generalization of Oberwolfach problem and Ct-factorizations of complete equipartite graph. J Combin Des, 2000, 8: 42-49
|
| 21 |
Liu J. The equipartite Oberwolfach problem with uniform tables. J Combin Theory Ser A, 2003, 101: 20-34
|
| 22 |
Niu M, Cao H. More results on cycle frames and almost resolvable cycle systems. Discrete Math, 2012, 312: 3392-3405
|
| 23 |
Niu M, Cao H. On the Oberwolfach Problem OP(5a, s). Utilitas Ma<?Pub Caret?>th (to appear)
|
| 24 |
Piotrowski W L. The solution of the bipartite analogue of the Oberwolfach problem. Discrete Math, 1991, 97: 339-356
|
| 25 |
Rees R. Two new direct product-type constructions for resolvable group divisible designs. J Combin Des, 1993, 1: 15-26
|
| 26 |
Rosa A, Znám Š.Packing pentagons into complete graphs: how clumsy can you get. Discrete Math, 1994, 128: 305-316
|
| 27 |
Šajna M. Cycle decompositions III, complete graphs and fixed length cycles. J Combin Des, 2012, 10: 27-78
|
| 28 |
Schönheim J, Bialostocki A. Packing and covering the complete graph with 4-cycles. Canad Math Bull, 1975, 18: 703-708
|
| 29 |
Stinson D R. Frames for Kirkman triple systems. Discrete Math, 1987, 65: 289-300
|
| 30 |
Vanstone S A, Stinson D R, Schellenberg P J, Rosa A, Rees R, Colbourn C J, Carter M W, Carter J E. Hanani triple systems. Israel J Math, 1993, 83: 305-319
|
/
| 〈 |
|
〉 |