一种用4-圈和8-圈对二分图的划分

证明了如果一个平衡二分图G包含4k个点,k≥2,并且对G中每一对满足x∈V1,y∈V2的不相邻顶点x和y成立d(x)+d(y)≥2k+1,则G包含k-2个4-圈和一个8-圈,并且这k-1个圈点不相交。

图中相互独立的4-圈和8-圈

设G是一个含有4k个顶点的简单图,若δ(G)≥2k,则G包含k-2个4-圈和1个8-圈,使得这k-1个圈是相互独立的。在此基础上证明了:若G是一个含有4k(k≥4)个顶点的图,δ(G)≥2k,则下列两种情况中至少有一种成立:(1)G包含k-3个4-圈和1个12-圈;(2)G包含k-4个4-圈和2个8-圈。且不论哪一种情况成立,这k-2个圈点不交。