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

Fronček, Dalibor; Kovář, Petr; Kubesa, Michael

Discrete Math. 310, No. 5, 1003-1015 (2010).

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

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