摘要
图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.
出处
《河北省科学院学报》
CAS
2012年第2期1-3,共3页
Journal of The Hebei Academy of Sciences
关键词
路核
路半核
(a
b)-剖分
路剖分猜想
Path kernel
Path semikernel
（a
b）-partition
Path Partition Conjecture
