论文摘要
我们设G为任意图,并且T（G）和c（G）分别定义为图G的最长路的阶数和周长,其中图G的周长c（G）定义如下：如果图G是无边的,则c（G）=1；如果图G是无圈的但至少包含一条边,则c（G）=2；最后,如果图G包含一个圈,则c（G）是图G中最长圈的长度。设一个图G,若对于任意一对满足a+b=τ（G）的正整数（a,b）,V有一个划分V=V1和V2满足T（<V1）)≤a和丁（<V2>）≤b,则称图G是T-可划分的。路划分猜想（PPC）为：任意图都是T-可划分的。如果c1,c2是正整数,并且V1,V2是满足c（）≤ci,i=1,2的V（G）的一个划分,则我们说（V1,V2）是图G的一个（c1,c2）-划分,并且G是（c1,c2）-可划分的。在文献[M.H.Nielsen,On a cycle partition problem,Discrete Math.308（2008）6339一6347]中,Nielsen提出圈划分的猜想：对于任意一对满足c1+c2=c（G）的正整数c1,c2,图G的顶点集V（G）存在一个划分V1和V2，使得集合Vi的导出图的周长至多为ci,i=1,2。在本文中,我们证明：一个图的最长圈是支配圈,则这个图是满足圈划分猜想的,并且我们还证明一个图的最长路是支配路,则这个图是满足路划分猜想的,此外,我们还证明：对于一个图G,如果有c（G）≥|V（G）|-3,则这个图G是圈可划分的。此外,我们证明：如果c1+c2=c（G）和2（|V（G）|-a（G））-c2≤c（G）,则G是（c1,c2）-可划分的。