Packing 5-cycles into balanced complete m-partite graphs for odd m
Tóm tắt
Let
$K_{n_{1},n_{2},\ldots,n_{m}}$
be a complete m-partite graph with partite sets of sizes n
1,n
2,…,n
m
. A complete m-partite graph is balanced if each partite set has n vertices. We denote this complete m-partite graph by K
m(n). In this paper, we completely solve the problem of finding a maximum packing of the balanced complete m-partite graph K
m(n), m odd, with edge-disjoint 5-cycles and we explicitly give the minimum leaves.
Tài liệu tham khảo
Alspach B, Gavlas H (2001) Cycle decompositions of K n and K n −I. J Comb Theory Ser B 81:77–99
Alspach B, Marshall S (1994) Even cycle decompositions of complete graphs minus a 1-factor. J Comb Des 2:441–458
Billington EJ, Fu H-L, Rodger CA (2001) Packing complete multipartite graphs with 4-cycles. J Comb Des 9:107–127
Billington EJ, Fu H-L, Rodger CA (2005) Packing λ-fold complete multipartite graphs with 4-cycles. Graphs Comb 21:169–185
Cavenagh NJ, Billington EJ (2000b) On decomposing complete tripartite graphs into 5-cycles. Australas J Comb 22:41–62
Lindner CC, Rodger CA (1992) Decomposition into cycle II: cycle systems. In: Dinitz JH, Stinson DR (eds) Contemporary design theory: a collection of surveys. Wiley, New York, pp 325–369
Rosa A, Znám S (1994) Packing pentagons into complete graphs: how clumsy can you get. Discrete Math 128:305–316
Wilson RM (1974) Some partitions of all triples into Steiner triple systems. In: Lecture notes in mathematics, vol 411. Springer, Berlin, pp 267–277