Almost resolvable maximum packings of complete graphs with 5-cycles

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

References

[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 K_n and K_n - 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 C_k-factorizations of K_2n-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 K_n 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 C_t-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(5_a, 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

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg