## 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.

### MSC:

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

### Keywords:

graph decompositions; graph labeling
Full Text:

### References:

 [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, (), 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] () [8] Häggkvist, R., A lemma on cycle decompositions, North-holland math. study, 115, 227-232, (1985) [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, (), 349-355 [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. 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.