图G的最长路的阶称为环游阶,记为τ（G）。顶点集V（G）的子集S称为图G的Pn-核,如果满足τ（G[S]）≤n-1且V（G）-S的每一个顶点v都与G[S]中阶为n-1路的端顶点相连。把顶点集V（G）剖分成A,B两部分,使得τ（G[A]）≤a和τ（G[B]）≤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）-剖分。%The detour order of a graph G,denoted by τ(G),is the order of a longest path in G.A subset S of V(G) is called a Pn-kernel of G if τ(G[S])≤ n-1 and every vertex v∈V(G)-S is adjacent to an end-vertex of a path n-1 in G[S].Apartition of the vertex set of G into two sets,A and B,such that τ(G[A])≤ a and τ(G[B])≤ b is called an(a,b)-partition of G.In this paper we show that any graph with girth g has a Pn+1-kernel for every n≤3g/2-1.Furtheremore,if τ(G)=a+b,1≤ a≤ b,G has girth greater than g≥2/3(a+1),then G has an(a,b)-partition.
展开▼
