Decompositions of complete multigraphs into cycles of varying lengths. (English) Zbl 1379.05087
Summary: We establish necessary and sufficient conditions for the existence of a decomposition of a complete multigraph into edge-disjoint cycles of specified lengths, or into edge-disjoint cycles of specified lengths and a perfect matching.
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C12 | Distance in graphs |
| 05C38 | Paths and cycles |
References:
| [1] | Alspach, B., Research Problem 3, Discrete Math., 36, 333 (1981) |
| [2] | Alspach, B.; Gavlas, H., Cycle decompositions of \(K_n\) and \(K_n - I\), J. Combin. Theory Ser. B, 81, 77-99 (2001) · Zbl 1023.05112 |
| [3] | Alspach, B.; Heinrich, K.; Liu, G. Z., Orthogonal factorizations of graphs, (Dinitz, J.; Stinson, D., Contemporary Design Theory: A Collection of Surveys (1992), Wiley: Wiley New York), 13-40 · Zbl 0779.05032 |
| [4] | Baranyai, Zs., On the factorization of the complete uniform hypergraph, Colloq. Math. Soc. János Bolyai, 10, 91-108 (1975) · Zbl 0306.05137 |
| [5] | Bermond, J-C.; Huang, C.; Sotteau, D., Balanced cycle and circuit designs: even cases, Ars Combin., 5, 293-318 (1978) · Zbl 0434.05020 |
| [6] | Bermond, J-C.; Sotteau, D., Cycle and circuit designs odd case, (Contributions to Graph Theory and Its Applications. Contributions to Graph Theory and Its Applications, Internat. Colloq., Oberhof, 1977 (1977), Tech. Hochschule Ilmenau: Tech. Hochschule Ilmenau Ilmenau), 11-32, (in German) · Zbl 0411.05025 |
| [7] | Bryant, D., Hamilton cycle rich two-factorisations of complete graphs, J. Combin. Des., 12, 147-155 (2004) · Zbl 1043.05095 |
| [8] | Bryant, D., Cycle decompositions of complete graphs, (Hilton, A.; Talbot, J., Surveys in Combinatorics 2007. Surveys in Combinatorics 2007, Proceedings of the 21st British Combinatorial Conference. Surveys in Combinatorics 2007. Surveys in Combinatorics 2007, Proceedings of the 21st British Combinatorial Conference, London Math. Soc. Lecture Note Ser., vol. 346 (2007), Cambridge University Press), 67-97 · Zbl 1131.05070 |
| [9] | Bryant, D., Packing paths in complete graphs, J. Combin. Theory Ser. B, 100, 206-215 (2010) · Zbl 1216.05111 |
| [10] | Bryant, D.; Horsley, D., Packing cycles in complete graphs, J. Combin. Theory Ser. B, 98, 1014-1037 (2008) · Zbl 1162.05037 |
| [11] | Bryant, D.; Horsley, D., Decompositions of complete graphs into long cycles, Bull. Lond. Math. Soc., 41, 927-934 (2009) · Zbl 1207.05153 |
| [12] | Bryant, D.; Horsley, D., An asymptotic solution to the cycle decomposition problem for complete graphs, J. Combin. Theory Ser. A, 117, 1258-1284 (2010) · Zbl 1213.05205 |
| [13] | Bryant, D.; Horsley, D.; Maenhaut, B., Decompositions into 2-regular subgraphs and equitable partial cycle decompositions, J. Combin. Theory Ser. B, 93, 67-72 (2005) · Zbl 1059.05083 |
| [14] | Bryant, D.; Horsley, D.; Maenhaut, B.; Smith, B. R., Cycle decompositions of complete multigraphs, J. Combin. Des., 19, 42-69 (2011) · Zbl 1205.05176 |
| [15] | 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 |
| [16] | Bryant, D.; Maenhaut, B., Decompositions of complete graphs into triangles and Hamilton cycles, J. Combin. Des., 12, 221-232 (2004) · Zbl 1042.05079 |
| [17] | Bryant, D.; Martin, G., Some results on decompositions of low degree circulant graphs, Australas. J. Combin., 45, 251-261 (2009) · Zbl 1207.05154 |
| [18] | Bryant, D.; Rodger, C. A., Cycle decompositions, (Colbourn, C. J.; Dinitz, J. H., The CRC Handbook of Combinatorial Designs (2007), CRC Press: CRC Press Boca Raton), 373-382 |
| [19] | Hanani, H., The existence and construction of balanced incomplete block designs, Ann. Math. Stat., 32, 361-386 (1961) · Zbl 0107.36102 |
| [20] | Hoffman, D. G.; Lindner, C. C.; Rodger, C. A., On the construction of odd cycle systems, J. Graph Theory, 13, 417-426 (1989) · Zbl 0704.05031 |
| [21] | Huang, C.; Rosa, A., On the existence of balanced bipartite designs, Util. Math., 4, 55-75 (1973) · Zbl 0273.05010 |
| [22] | Kirkman, T. P., On a problem in combinations, Cambridge and Dublin Math. J., 2, 191-204 (1847) |
| [23] | Lin, C.; Shyu, T-W., A necessary and sufficient condition for the star decomposition of complete graphs, J. Graph Theory, 23, 361-364 (1996) · Zbl 0880.05069 |
| [24] | Lucas, E., Récreations Mathématiqués, Vol. II (1892), Gauthier-Villars: Gauthier-Villars Paris |
| [25] | Maenhaut, B.; Smith, B. R., Face 2-colourable embeddings with faces of specified lengths, J. Graph Theory, 82, 296-311 (2016) · Zbl 1342.05090 |
| [26] | Rosa, A.; Huang, C., Another class of balanced graph designs: balanced circuit designs, Discrete Math., 12, 269-293 (1975) · Zbl 0306.05013 |
| [27] | Šajna, M., Cycle decompositions III: complete graphs and fixed length cycles, J. Combin. Des., 10, 27-78 (2002) · Zbl 1033.05078 |
| [28] | Smith, B. R., Decompositions of Generalised Complete Graphs (2009), The University of Queensland, PhD Thesis |
| [29] | Smith, B. R., Cycle decompositions of complete multigraphs, J. Combin. Des., 18, 85-93 (2010) · Zbl 1216.05117 |
| [30] | Tarsi, M., Decomposition of complete multigraphs into stars, Discrete Math., 26, 273-278 (1979) · Zbl 0421.05016 |
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.
