關于路核和路剖分的研究.pdf

1、河北工業(yè)大學碩士學位論文關于路核和路剖分的研究姓名：王寶麗申請學位級別：碩士專業(yè)：應用數(shù)學指導教師：何文杰20090601q 4 . ? ? . ~ B ? ? dON PATH KERNELS AND PARTITIONSABSTRACTThe detour order of a graph G, denoted by τ(G), is the order of a longestpath in G. A subset S of V

2、(G) is called a Pn-kernel of G if τ(G[S]) ≤ n?1and every vertex v ∈ V (G) ? S is adjacent to an end-vertex of a path oforder n ? 1 in G[S]. A partition of the vertex set of G into two sets, A andB, such that τ(G[A]) ≤ a

3、and τ(G[B]) ≤ b is called an (a, b)-partition ofG. In this paper we show that any graph with girth g has a Pn+1-kernelfor every n 23(a + 1), then G has an (a, b)-partition.KEY WORDS: path kernel, path semikernel, (a, b)