关于路核和路剖分的研究

摘要

图G最长路的阶称为环游阶，记为Υ(G).顶点集V(G)的子集S称为图G的Pn-核，如果满足Υ(G[S])≤n-1且V(G)-S的每一个项点υ与G(S)中阶为n-1路的端顶点相连.把顶点集V(G)剖分成A，B两部分，使得Υ(G[S])≤a和(G[S])≤b，此部分称为G的一个(a,b)-剖分.本文证明了对于n<3g/2-1的正整数，任意围长为g的图都有一个Pn+1-核.并且还得到，如果Υ(G)=a+b,其中1≤a≤b,图G的围长g>2/3(a+1)，那么G有一个(a,b)-剖分.