Packing 5-cycles into balanced complete m-partite graphs for odd m

Springer Science and Business Media LLC - Tập 14 - Trang 323-329 - 2007
Ming-Hway Huang1, Chin-Mei Fu2, Hung-Lin Fu3
1Department of Computer Science and Information Engineering, Yuanpei Institute of Science and Technology, Hsinchu, Taiwan
2Department of Mathematics, Tamkang University, Tamsui, Taipei Shien, Taiwan
3Department of Applied Mathematics, National Chiao Tung University, Hsinchu, Taiwan

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