Decompositions of complete graphs into blown-up cycles \(C_m\)[2]. (English) Zbl 1230.05234

Summary: Let \(C_m[\overline K_2]\) stand for a cycle \(C_m\) in which every vertex is replaced by two isolated vertices and every edge by \(K_{2,2}\). We prove that the complete graph \(K_{8mk+1}\) can be decomposed into graphs isomorphic to \(C_m [\overline K_2]\) for any \(m\geq 3, k>0\). Decompositions of complete graphs into certain collections of even cycles are obtained as a corollary. Also some special cases of Alspach Conjecture are solved in this article. All proofs are constructive and use both graph theory and design theory techniques.


05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
Full Text: DOI


[1] 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
[2] Bermond, J. C.; Huang, C.; Sotteau, D., Balanced cycle and circuit designs: Even case, Ars. Combin., 5, 293-318 (1978) · Zbl 0434.05020
[3] Bryant, D., Cycle decompositions of complete graphs, (Surveys in Combinatorics 2007. Surveys in Combinatorics 2007, London Math. Soc. Lecture Note Ser., vol. 346 (2007), Cambridge Univ Press: Cambridge Univ Press Cambridge), 67-97 · Zbl 1131.05070
[4] Cavenagh, N., Decompositions of complete tripartite graphs into \(k\)-cycles, Australas. J. Combin., 18, 193-200 (1998) · Zbl 0924.05051
[5] Cavenagh, N. J.; Billington, E. J., Decompositions of complete multipartite graphs into cycles of even length, Graphs Combin., 16, 49-65 (2000) · Zbl 0944.05083
[6] Cockayne, J. E.; Hartnell, B. L., Edge partitions of complete multipartite graphs into equal length circuits, J. Combin. Theory, Ser. B, 23, 174-183 (1977) · Zbl 0313.05121
[7] (Colbourn, C. J.; Dinitz, J. H., The CRC Handbook of Combinatorial Designs (2007), Discrete Mathematics and its Applications: Discrete Mathematics and its Applications Boca Raton, FL) · Zbl 1101.05001
[8] Häggkvist, R., A lemma on cycle decompositions, North-Holland Math. Study, 115, 227-232 (1985) · Zbl 0577.05045
[9] Muthusamy, A.; Paulraja, P., Factorizations of product graphs into cycles of uniform length, Graphs Combin., 11, 69-90 (1995) · Zbl 0822.05054
[10] Ramírez-Alfonsín, J. L., Cycle decompositions of complete and complete multipartite graphs, Australas. J. Combin., 11, 233-238 (1995) · Zbl 0842.05073
[11] Rosa, A., On certain valuations of the vertices of a graph, (Theory Graphs, Int. Symp. Rome 1966 (1967), Gordon and Breach: Gordon and Breach NY and Dunod Paris), 349-355 · Zbl 0193.53204
[12] Sajna, M., Cycle decompositions III, J. Combin. Des., 10, 27-78 (2002) · Zbl 1033.05078
[13] Sotteau, D., Decompositions of \(K_{m, n}, K_{m, n}^\ast\) into cycles (circuits) of length \(2 k\), J. Combin. Theory, Ser. B, 30, 75-81 (1981) · Zbl 0463.05048
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.