完全r部图K_r(t)的{C_3,C_(2k)}-强制分解(k≥4)的渐近存在性

Mandatory decompositions of complete multipartite graphs into cycles of lengths 3 and 2k(k≥4)

研究基于顶点集V=∪ir=1Vi(其中|Vi|=t,i=1,2,…,r)的完全r部图Kr(t)的3圈和2k圈{C3,C2k}-强制分解(k≥4)的存在性问题.通过构造并运用Kr(t)的两种分解法,证明了Kr(t)的{C3,C2k}-强制分解(k≥4)的渐近存在性,即对于任意给定的正整数k≥4,存在常数r0(k)=5k+2,使得当r≥r0(k)时,Kr(t)的{C3,C2k}-强制分解存在的必要条件也是充分的.

In this paper, the existence problem of a{Ca,C2k}-mandatory decomposition of Kr（t） was discussed. Through constructing and applying two decomposition methods of Kr（t）, the paper proved that the necessary conditions for the existence of a {C3, C2k }-mandatory decomposition of Kr （t）（k ≥ 4） are also sufficient whenever r ≥ 5k＋2.