Contents

-

Path Kernels and Partitions

Jean E. Dunbar1, Marietjie Frick2
1Converse College Spartanburg, SC 29302 USA
2University of South Africa Pretoria, 0001 South Africa

Abstract

Let τ(G) denote the number of vertices in a longest path of the graph G=(V,E). A subset K of V is called a Pn-\emph{kernel} of G if τ(G[K])n1 and every vertex vV(GK) is adjacent to an end-vertex of a path of order n1 in G[K].
A partition {A,B} of V is called an (a,b)-partition if τ(G[A])a and τ(G[B])b.
We show that any graph with girth greater than n3 has a Pn-kernel and that every graph has a Pγ-kernel. As corollaries of these results, we show that if τ(G)=a+b and G has girth greater than a2 or a6, then G has an (a,b)-partition.