Decompositions of some classes of dense graphs into cycles of lengths 4 and 8. (English) Zbl 1469.05141
Summary: For an even graph \(G\) and non-negative integers \(r\) and \(s\), the pair \((r,\,s)\) is an admissible pair if \(4r+8s=|E(G)|\). If \(G\) admits a decomposition into \(r\) copies of \(C_4\), the cycle of length four, and \(s\) copies of \(C_8\), the cycle of length eight, for every admissible pair \((r,\,s)\), then \(G\) has a \(\{C_4^r,\,C_8^s\}\)-decomposition. In this paper, a necessary and sufficient condition is obtained for the existence of a \(\{C_4^r,\,C_8^s\}\)-decomposition of the complete \(k\)-partite graph \(K_{a_1,\,a_2,\dots,a_k}\), where \(k\ge 3\). Further, a characterization is obtained for the graph \(K_m\times K_n,\) where \(\times\) denotes the tensor product of graphs, to admit a \(\{C_4^r,\,C_8^s\}\)-decomposition.
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
References:
| [1] | Assaf, A., Modified group divisible designs, ARS Combin., 29, 13-20 (1990) · Zbl 0702.05014 |
| [2] | Asplund, J.; Chaffee, J.; Hammer, JM, Decomposition of a complete bipartite multigraph into arbitrary cycle sizes, Graphs Combin., 33, 715-728 (2017) · Zbl 1371.05225 · doi:10.1007/s00373-017-1817-0 |
| [3] | Balakrishnan, R.; Ranganathan, K., A Text Book of Graph Theory (2012), New York: Springer, New York · Zbl 1254.05001 · doi:10.1007/978-1-4614-4529-6 |
| [4] | Balakrishnan, R.; Bermond, J-C; Paulraja, P.; Yu, M-L, On Hamilton cycle decompositions of the tensor product of complete graphs, Discr. Math., 268, 49-58 (2003) · Zbl 1027.05076 · doi:10.1016/S0012-365X(02)00680-5 |
| [5] | Bahmanian, MA; Šajna, M., Decomposing complete equipartite multigraphs into cycles of variable lengths: the Amalgamation-detachment approach, J. Combin. Des., 24, 165-183 (2016) · Zbl 1338.05208 · doi:10.1002/jcd.21419 |
| [6] | Billington, EJ, Decomposing complete tripartite graphs into cycles of lengths 3 and 4, Discr. Math., 197, 198, 123-135 (1999) · Zbl 0930.05072 · doi:10.1016/S0012-365X(98)00227-1 |
| [7] | Billington, EJ; Cavenagh, NJ, Decomposition of complete multipartite graphs into cycles of even length, Graphs Combin., 16, 49-65 (2000) · Zbl 0944.05083 · doi:10.1007/s003730050003 |
| [8] | Billington, EJ; Hoffman, DG; Maenhaut, BM, Group divisible pentagon systems, Utilitas Math., 55, 211-219 (1999) · Zbl 0938.05020 |
| [9] | Billington, EJ; Cavenagh, NJ; Smith, BR, Path and cycle decompositions of complete equipartite graphs: four parts, Discr. Math., 309, 3061-3073 (2009) · Zbl 1202.05070 · doi:10.1016/j.disc.2008.08.009 |
| [10] | Billington, EJ; Cavenagh, NJ; Smith, BR, Path and cycle decompositions of complete equipartite graphs: 3 and 5 parts, Discr. Math., 310, 241-254 (2010) · Zbl 1200.05135 · doi:10.1016/j.disc.2008.09.003 |
| [11] | Bryant, D.; Horsley, D.; Pettersson, W., Cycle decompositions V: complete graphs into cycles of arbitrary lengths, Proc. Lond. Math. Soc., 108, 1153-1192 (2014) · Zbl 1296.05044 · doi:10.1112/plms/pdt051 |
| [12] | Bryant, D.; Horsley, D.; Maenhaut, B.; Smith, BR, Decompositions of complete multigraphs into cycles of varying lengths, J. Combin. Theory Ser. B, 129, 79-106 (2018) · Zbl 1379.05087 · doi:10.1016/j.jctb.2017.09.005 |
| [13] | Cavenagh, NJ, Decompositions of complete tripartite graphs into \(k\)-cycles, Aust. J. Combin., 18, 193-200 (1998) · Zbl 0924.05051 |
| [14] | Chou, CC; Fu, CM; Huang, WC, Decomposition of \(K_{m,\, n}\) into short cycles, Discr. Math., 197, 198, 195-203 (1999) · Zbl 0934.05106 · doi:10.1016/S0012-365X(99)90063-8 |
| [15] | Chou, CC; Fu, CM, Decomposition of \(K_{m,\, n}\) into \(4\)-cycles and \(2t\)-cycles, J. Comb. Optim., 14, 205-218 (2007) · Zbl 1132.05047 · doi:10.1007/s10878-007-9060-x |
| [16] | Fu, CM; Huang, KC; Mishima, M., Decomposition of complete bipartite graphs into cycles of distinct even lengths, Graphs Combin., 32, 1397-1413 (2016) · Zbl 1342.05072 · doi:10.1007/s00373-015-1664-9 |
| [17] | Ganesamurthy, S.; Paulraja, P., \(2p\)-cycle decompositions of some regular graphs and digraphs, Discr. Math., 341, 2197-2210 (2018) · Zbl 1388.05156 · doi:10.1016/j.disc.2018.04.022 |
| [18] | Ganesamurthy, S.; Manikandan, RS; Paulraja, P., Decompositions of some regular graphs and digraphs into cycles of length \(4p,\) Australas, J. Combin., 79, 215-233 (2021) · Zbl 1465.05143 |
| [19] | Ganesamurthy, S.; Paulraja, P., Decompositions of complete tripartite graphs into cycles of lengths \(3\) and \(6,\) Australas, J. Combin., 73, 220-241 (2019) · Zbl 1411.05218 |
| [20] | Hanani, H., Balanced incomplete block designs and related designs, Discr. Math., 11, 255-369 (1975) · Zbl 0361.62067 · doi:10.1016/0012-365X(75)90040-0 |
| [21] | Huang, MH; Fu, HL, \((4,5)\)-Cycle systems of complete multipartite graphs, Taiwan J. Math., 16, 999-1006 (2012) · Zbl 1245.05072 |
| [22] | Lindner, CC; Rodger, CA, Design Theory (2009), Boca Raton: CRC Press, Boca Raton · Zbl 1157.68403 |
| [23] | Manikandan, RS; Paulraja, P., \(C_p\)-decompositions of some regular graphs, Discr. Math., 306, 429-451 (2006) · Zbl 1087.05048 · doi:10.1016/j.disc.2005.08.006 |
| [24] | Manikandan, RS; Paulraja, P., \(C_5\)-decompositions of the tensor product of complete graphs, Aust. J. Combin., 37, 285-294 (2007) · Zbl 1120.05071 |
| [25] | Manikandan, RS; Paulraja, P., \(C_7\)-decompositions of the tensor product of complete graphs, Discuss. Math. Graph Theory, 37, 523-535 (2017) · Zbl 1366.05081 · doi:10.7151/dmgt.1936 |
| [26] | Manikandan, RS; Paulraja, P.; Sivakaran, T., \(p^2\)-Cycle decomposition of the tensor product of Complete Graphs, Aust. J. Combin., 73, 107-131 (2019) · Zbl 1411.05228 |
| [27] | Muthusamy, A.; Shanmuga Vadivu, A., Cycle frames of complete multipartite multigraphs-III, J. Combin. Des., 22, 473-487 (2014) · Zbl 1305.05203 · doi:10.1002/jcd.21373 |
| [28] | Paulraja, P.; Srimathi, R., Decompositions of tensor product of complete graphs into cycles of lengths \(3\) and \(6\), Discuss. Math. Graph Theory, 41, 249-266 (2021) · Zbl 1453.05104 · doi:10.7151/dmgt.2178 |
| [29] | Smith, BR, Decomposing complete equipartite graphs into cycles of length \(2p\), J. Combin. Des., 16, 244-252 (2008) · Zbl 1149.05026 · doi:10.1002/jcd.20173 |
| [30] | Smith, BR, Complete equipartite \(3p\)-cycle systems, Aust. J. Combin., 45, 125-138 (2009) · Zbl 1207.05108 |
| [31] | Smith, BR, Decomposing complete equipartite graphs into odd square-length cycles: number of parts odd, J. Combin. Des., 18, 401-414 (2010) · Zbl 1208.05118 · doi:10.1002/jcd.20268 |
| [32] | Smith, BR, Cycle decompositions of \(\lambda \)-fold complete equipartite graphs, Aust. J. Combin., 47, 145-156 (2010) · Zbl 1218.05151 |
| [33] | Sotteau, D., Decomposition of \(K_{m,n}(K^*_{m,n})\) into cycles (circuits) of length \(2k\), J. Combin. Theory. Ser. B, 30, 75-81 (1981) · Zbl 0463.05048 · doi:10.1016/0095-8956(81)90093-9 |
| [34] | Tarsi, M., Decomposition of a complete multigraph into simple paths: nonbalanced handcuffed designs, J. Combin. Theory. Ser. A, 34, 60-70 (1983) · Zbl 0511.05024 · doi:10.1016/0097-3165(83)90040-7 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
