Mycielski图的P_4分解

给定图G=(V,E),G的Mycielski图μ(G)被定义为一个新图:V(μ(G))=V∪V'∪{w},其中V'={y'｜y∈V};E(μ(G))=E∪{xy'｜xy∈E}∪{wy'｜y'∈V'},称点y'为y的复制点.文章证明了连通图G的Mycielski图存在P4分解当且仅当G的阶数能被3整除.此外我们还给出了Mycielski图的P4分解的一个多项式算法.

Cartesian积图的分解

若图G的边集能划分成两两不相交的若干个子集,使得每个子集都导出相同的子图H,则称G存在H分解。两个图Gi=(Vi,Ei)(i=1,2)的Cartesian积,记作G1□G2,其顶点集V=V1×V2,边集E={((u1,u2),(v1,v2))|u1=v1∈V1,u2v2∈E2或u2=v2∈V2,u1v1∈E1}。本文给出了路和圈的Cartesian积图存在P4分解的充要条件。

完全二部图的P_(4k-1)-因子分解

如果完全二部图Km,n的边集可以划分为Km,n的Pv-因子,则称Km,n存在Pv-因子分解.当v是偶数时,Ushio和Wang给出了Km,n存在Pv-因子分解的充分必要条件.Ushio同时提出了当v是奇数时Km,n存在Pv-因子分解的猜想,但是至今为止仅知当v=3时Ushio猜想成立.对于正整数k,本文证明Km,n存在P4k-1-因子分解的充分必要条件是:(1)(2k-1)m≤2kn,(2)(2k-1)n≤2km,(3)m+n=0(mod4k-1),(4)(4k-1)mn/[2(2k-1)(m+n)]是整数.即证明了对于任意正整数k,当v=4k-1时Ushio猜想成立.