RESEARCH ARTICLE

Almost resolvable maximum packings of complete graphs with 5-cycles

  • Min ZHOU ,
  • Haitao CAO
Expand
  • Institute of Mathematics, Nanjing Normal University, Nanjing 210023, China

Received date: 08 Nov 2013

Accepted date: 20 Aug 2014

Published date: 12 Feb 2015

Copyright

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg

Abstract

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 nk (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.

Cite this article

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

DOI

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

DOI

5
Assaf B, Hartman A. Resolvable group divisible designs with block size 3. Discrete Math, 1989, 77: 5-20

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

14
Hoffman D G, Schellenberg P J. The existence of Ck-factorizations of K2n-F.Discrete Math, 1991, 97: 243-250

DOI

15
Horsley D. Maximum packings of the complete graph with uniform length cycles. J Graph Theory, 2011, 68: 1-7

DOI

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

DOI

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

DOI

21
Liu J. The equipartite Oberwolfach problem with uniform tables. J Combin Theory Ser A, 2003, 101: 20-34

DOI

22
Niu M, Cao H. More results on cycle frames and almost resolvable cycle systems. Discrete Math, 2012, 312: 3392-3405

DOI

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

DOI

25
Rees R. Two new direct product-type constructions for resolvable group divisible designs. J Combin Des, 1993, 1: 15-26

DOI

26
Rosa A, Znám Š.Packing pentagons into complete graphs: how clumsy can you get. Discrete Math, 1994, 128: 305-316

DOI

27
Šajna M. Cycle decompositions III, complete graphs and fixed length cycles. J Combin Des, 2012, 10: 27-78

DOI

28
Schönheim J, Bialostocki A. Packing and covering the complete graph with 4-cycles. Canad Math Bull, 1975, 18: 703-708

DOI

29
Stinson D R. Frames for Kirkman triple systems. Discrete Math, 1987, 65: 289-300

DOI

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

DOI

Outlines

/