Decompositions of complete graphs into blown-up cycles C-m[2]

作者：Froncek Dalibor^*; Kovar Petr; Kubesa Michael

来源：Discrete Mathematics, 2010, 310(5): 1003-1015.

DOI：10.1016/j.disc.2009.10.018

• Graph decompositions
• Graph labeling

Let C-m vertical bar(K) over bar (2)vertical bar stand for a cycle C-m in which every vertex is replaced by two isolated vertices and every edge by K-2,K-2. We prove that the complete graph K8mk+1 can be decomposed into graphs isomorphic to C-m vertical bar(K) over bar (2)vertical bar for any m >= 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.

• 出版日期2010-3-6