Almost resolvable maximum packings of complete graphs with 5-cycles

doi:10.1007/s11464-015-0425-7

Front. Math. China

2015, Vol. 10

Issue (2) : 461-475 https://doi.org/10.1007/s11464-015-0425-7

RESEARCH ARTICLE

Almost resolvable maximum packings of complete graphs with 5-cycles

Min ZHOU,Haitao CAO(

)

Institute of Mathematics, Nanjing Normal University, Nanjing 210023, China

Download: PDF(151 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

Let X be the vertex set of K_nA k-cycle packing of K_n is a triple (X,C,L), where C is a collection of edge disjoint k-cycles of K_n and L is the collection of edges of K_n 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 K_n, denoted by k-RMCP(n), is a resolvable k-cycle packing of K_n, (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.

Keywords Cycle packing resolvable maximum cycle packing cycle frame

Corresponding Author(s): Haitao CAO

Issue Date: 12 February 2015

Cite this article:

Min ZHOU,Haitao CAO. Almost resolvable maximum packings of complete graphs with 5-cycles[J]. Front. Math. China, 2015, 10(2): 461-475.

URL:

https://academic.hep.com.cn/fmc/EN/10.1007/s11464-015-0425-7
https://academic.hep.com.cn/fmc/EN/Y2015/V10/I2/461

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 https://doi.org/10.1007/s00493-010-2525-z
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 https://doi.org/10.1016/0097-3165(89)90059-9
5	Assaf B, Hartman A. Resolvable group divisible designs with block size 3. Discrete Math, 1989, 77: 5-20 https://doi.org/10.1016/0012-365X(89)90346-4
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 https://doi.org/10.1007/s00373-010-0967-0
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 https://doi.org/10.1016/j.jctb.2007.12.004
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 https://doi.org/10.1016/j.disc.2011.07.008
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 https://doi.org/10.1016/0097-3165(92)90099-G
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 https://doi.org/10.1016/0012-365X(94)90375-1
14	Hoffman D G, Schellenberg P J. The existence of Ck-factorizations of K2n-F.Discrete Math, 1991, 97: 243-250 https://doi.org/10.1016/0012-365X(91)90440-D
15	Horsley D. Maximum packings of the complete graph with uniform length cycles. J Graph Theory, 2011, 68: 1-7 https://doi.org/10.1002/jgt.20536
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 https://doi.org/10.1002/jcd.20204
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 https://doi.org/10.1002/(SICI)1520-6610(2000)8:1<42::AID-JCD6>3.0.CO;2-R
21	Liu J. The equipartite Oberwolfach problem with uniform tables. J Combin Theory Ser A, 2003, 101: 20-34 https://doi.org/10.1016/S0097-3165(02)00011-0
22	Niu M, Cao H. More results on cycle frames and almost resolvable cycle systems. Discrete Math, 2012, 312: 3392-3405 https://doi.org/10.1016/j.disc.2012.08.002
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 https://doi.org/10.1016/0012-365X(91)90449-C
25	Rees R. Two new direct product-type constructions for resolvable group divisible designs. J Combin Des, 1993, 1: 15-26 https://doi.org/10.1002/jcd.3180010104
26	Rosa A, Znám ?.Packing pentagons into complete graphs: how clumsy can you get. Discrete Math, 1994, 128: 305-316 https://doi.org/10.1016/0012-365X(94)90121-X
27	?ajna M. Cycle decompositions III, complete graphs and fixed length cycles. J Combin Des, 2012, 10: 27-78 https://doi.org/10.1002/jcd.1027
28	Sch?nheim J, Bialostocki A. Packing and covering the complete graph with 4-cycles. Canad Math Bull, 1975, 18: 703-708 https://doi.org/10.4153/CMB-1975-123-4
29	Stinson D R. Frames for Kirkman triple systems. Discrete Math, 1987, 65: 289-300 https://doi.org/10.1016/0012-365X(87)90060-4
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 https://doi.org/10.1007/BF02784058

Viewed

Full text

Abstract

Cited

Shared

Discussed