Abstract:
The detour order of a graph G, denoted by (G), is the order of a longest
path in G. If a and b are positive integers and the vertex set of G can be partitioned
into two subsets A and B such that (hAi) ≤ a and (hBi) ≤ b, we say
that (A,B) is an (a, b)-partition of G. If equality holds in both instances, we
call (A,B) an exact (a, b)-partition. The Path Partition Conjecture (PPC)
asserts that if G is any graph and a, b any pair of positive integers such
that (G) = a + b, then G has an (a, b)-partition. The Strong PPC asserts
that under the same circumstances G has an exact (a, b)-partition. While
a substantial body of work in support of the PPC has been developed over
the past three decades, no results on the Strong PPC have yet appeared in
the literature. In this paper we prove that the Strong PPC holds for a ≤ 8.
