Cycle Partition And Path Partition Of Some Graphs

Let G be any graph, and letτ(G) and c(G) denote the order of a longest path and the circumference of G, respectively, where c(G) is defined as follows:If G is edgeless then c(G)= 1; if G is acyclic but contains an edge then c(G)= 2; finally, if G contains a cycle then c(G) is the length of a longest cycle in G. Let G be a graph, for every pair a, b of positive integers satisfying a+b=τ(G), if the vertex set of G admits a partition into two sets V1 and V2, such thatτ()≤b, then G is said to beτ-partitionable. The path partition conjecture (PPC) claims that every graph isτ-partitionable.If c1 and c2 are positive integers and (V1,V2) is a partition of V(G), such that c()≤ci,i = 1,2, then we say that (V1V2) is a (c1,c2)-partition of G and that G is (c1,c2)-partitionable.In [M.H. Nielsen, On a cycle partition problem, Discrete Math.308(2008)6339-6347] it is conjectured that for every pair c1, c2 of positive integers satisfying c1+c2= c(G), the vertex set of G admits a partition into two sets V1 and V2, such that Vi induces a graph of circumference at most ci, i = 1,2.In this paper, we prove that if G has a longest cycle that is dominating, then G is c-partitionable; and we prove that a graph with a longest path that is dominating satisfies PPC. Moreover, we prove that G is c-partitionable if c(G)≥|V(G)| - 3, and G admits a (c1,c2)-partition if c1+c2= c(G) and 2(| V(G)|-a(G))-c2≤c(G).