Abstract :
For a graph G, let σ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=∑i=1kai is given and σ2(G)⩾n+k−1, then for any k distinct vertices v1,…,vk, G can be decomposed into vertex-disjoint paths P1,…,Pk such that |V(Pi)|=ai and vi is an endvertex of Pi. Enomoto and Ota (J. Graph Theory 34 (2000) 163) verified the conjecture for the case where all ai⩽5, and the case where k⩽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=∑i=1kai is given and σ2(G)⩾∑i=1kmax(⌊43ai⌋,ai+1)−1, then for any k distinct vertices v1,…,vk, G can be decomposed into vertex-disjoint paths P1,…,Pk such that |V(Pi)|=ai and vi is an endvertex of Pi for all i. This theorem implies that the conjecture is true for the case where all ai⩽5 which was proved in (J. Graph Theory 34 (2000) 163–169).
