×

zbMATH — the first resource for mathematics

Decomposing complete equipartite multigraphs into cycles of variable lengths: the amalgamation-detachment approach. (English) Zbl 1338.05208
Summary: Using the technique of amalgamation-detachment, we show that the complete equipartite multigraph \(\lambda K_{n\times m}\) can be decomposed into cycles of lengths \(c_1m,\ldots,c_km\) (plus a 1-factor if the degree is odd) whenever there exists a decomposition of \(\lambda mK_n\) into cycles of lengths \(c_1,\ldots,c_k\) (plus a 1-factor if the degree is odd). In addition, we give sufficient conditions for the existence of some other, related cycle decompositions of the complete equipartite multigraph \(\lambda K_{n\times m}\).

MSC:
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C38 Paths and cycles
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alspach, Research Problem 3, Discrete Math 36 (1981)
[2] Archdeacon, Cycle systems in the complete bipartite graph minus a one-factor, Discrete Math 284 pp 37– (2004) · Zbl 1049.05020 · doi:10.1016/j.disc.2003.11.021
[3] Bahmanian, What are graph amalgamations?, Recent Results in Designs and Graphs: a Tribute to Lucia Gionfriddo, Quaderni di matematica 28 pp 63– (2013)
[4] Billington, Decomposition of complete multipartite graphs into cycles of even length, Graphs Combin 16 pp 49– (2000) · Zbl 0944.05083 · doi:10.1007/s003730050003
[5] Billington, Path and cycle decompositions of complete equipartite graphs: 3 and 5 parts, Discrete Math 310 pp 241– (2010) · Zbl 1200.05135 · doi:10.1016/j.disc.2008.09.003
[6] Billington, Path and cycle decompositions of complete equipartite graphs: four parts, Discrete Math 309 pp 3061– (2009) · Zbl 1202.05070 · doi:10.1016/j.disc.2008.08.009
[7] Billington, Group divisible pentagon systems, Utilitas Math 55 pp 211– (1999) · Zbl 0938.05020
[8] D. Bryant personal communication 2014
[9] Bryant, Cycle decompositions of complete multigraphs, J Combin Des 19 pp 42– (2011) · Zbl 1205.05176 · doi:10.1002/jcd.20263
[10] Bryant, Cycle decompositions V: Complete graphs into cycles of arbitrary lengths, Proc London Math Soc 108 pp 1153– (2014) · Zbl 1296.05044 · doi:10.1112/plms/pdt051
[11] Cavenagh, Decompositions of complete tripartite graphs into k-cycles, Australas J Combin 18 pp 193– (1998) · Zbl 0924.05051
[12] Chou, Decomposition of Km,n into 4-cycles and 2t-cycles, J Comb Optim 14 pp 205– (2007) · Zbl 1132.05047 · doi:10.1007/s10878-007-9060-x
[13] Chou, Decomposition of 2Km,n into short cycles, Util Math 58 pp 3– (2000)
[14] Chou, Decomposition of Km,n into short cycles, Discrete Math 197/198 pp 195– (1999) · Zbl 0934.05106 · doi:10.1016/S0012-365X(99)90063-8
[15] Hanani, Balanced incomplete block designs and related designs, Discrete Math 11 pp 255– (1975) · Zbl 0361.62067 · doi:10.1016/0012-365X(75)90040-0
[16] Hilton, Hamiltonian decompositions of complete graphs, J Combin Theory B 36 pp 125– (1984) · Zbl 0542.05044 · doi:10.1016/0095-8956(84)90020-0
[17] Hilton, Hamilton decompositions of complete regular s-partite graphs, Discrete Math 58 pp 63– (1986) · Zbl 0593.05047 · doi:10.1016/0012-365X(86)90186-X
[18] Horsley, Decomposing various graphs into short even-length cycles, Ann Comb 16 pp 571– (2012) · Zbl 1256.05189 · doi:10.1007/s00026-012-0147-4
[19] Huang, (4,5)-cycle systems of complete multipartite graphs, Taiwanese J Math 16 pp 999– (2012)
[20] Laskar, On decomposition of r-partite graphs into edge-disjoint Hamilton circuits, Discrete Math 14 pp 265– (1976) · Zbl 0322.05128 · doi:10.1016/0012-365X(76)90039-X
[21] Ma, Cycle decompositions of Kn,n-I, SIAM J Discrete Math 20 pp 603– (2006) · Zbl 1124.05077 · doi:10.1137/050626363
[22] Manikandan, Cp-decompositions of some regular graphs, Discrete Math 306 pp 429– (2006) · Zbl 1087.05048 · doi:10.1016/j.disc.2005.08.006
[23] Smith, Cycle decompositions of \(\lambda\)-fold complete equipartite graphs, Australas J Combin 47 pp 145– (2010) · Zbl 1218.05151
[24] Smith, Decomposing complete equipartite graphs into odd square-length cycles: number of parts odd, J Combin Des 18 pp 401– (2010) · Zbl 1208.05118 · doi:10.1002/jcd.20268
[25] Smith, Complete equipartite 3p-cycle systems, Australas J Combin 45 pp 125– (2009) · Zbl 1207.05108
[26] Smith, Decomposing complete equipartite graphs into cycles of length 2p, J Combin Des 16 pp 244– (2008) · Zbl 1149.05026 · doi:10.1002/jcd.20173
[27] Smith, Decomposing complete equipartite graphs into short odd cycles, Electron J Combin 17 (2010) · Zbl 1231.05151
[28] Smith, Decomposing complete equipartite graphs into short even cycles, J Combin Des 19 pp 131– (2011) · Zbl 1216.05118 · doi:10.1002/jcd.20265
[29] Sotteau, Decomposition of Km,n (Km,n*) into cycles (circuits) of length 2k, J Combin Theory Ser B 30 pp 75– (1981) · Zbl 0463.05048 · doi:10.1016/0095-8956(81)90093-9
[30] deWerra, Combinatorial programming: methods and applications pp 337– (1975)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.