Graph partition into paths containing specified vertices

For a graph G, let sigma(2)(G) denote the minimum degree sum of a pair of nonadjacent vertices. Suppose G is a graph of order n. Enomoto and Ota (J. Graph Theory 34 (2000) 163-169) conjectured that, if a partition n = Sigma(i=1)(k) a(i) is given and sigma(2)(G) greater than or equal to n + k - 1, then for any k distinct vertices v(1),...,v(k), G can be decomposed into vertex-disjoint paths P-1,...,P-k such that \V(P-i)\ = a(i) and v(i) is an endvertex of P-i. Enomoto and Ota (J. Graph Theory 34 (2000) 163) verified the conjecture for the case where all a(i) less than or equal to 5, and the case where k less than or equal to 3. In this paper, we prove the following theorem, with a stronger assumption of the conjecture. Suppose G is a graph of order n. If a partition n = Sigma(i=1)(k) a(i) is given and sigma(2)(G) greater than or equal to Sigma(i=1)(k) max([4/3a(i)], a(i) + 1) - 1, then for any k distinct vertices v(1),...,v(k), G can be decomposed into vertex-disjoint paths P-1,..., P-k. such that \V(P-i)\ = a(i) and v(i) is an endvertex of P-i for all i. This theorem implies that the conjecture is true for the case where all a(i) less than or equal to 5 which was proved in (J. Graph Theory 34 (2000) 163-169). (C) 2002 Elsevier Science B,V. All rights reserved.