Minimum degree and pan-k-linked graphs

For a k-inked graph G and a vector (S) over bar of 2k distinct vertices of G, an (S) over bar -linkage is a set of k vertex-disjoint paths joining particular vertices of (S) over bar. Let T denote the minimum order of an (S) over bar -linkage in G. A graph G is said to be pan-k-linked if it is k-linked and for all vectors (S) over bar of 2k distinct vertices of G, there exists an (S) over bar -linkage of order t for all t such that T <= t <= |V(G)|. We first show that if k >= 1 and G is a graph on n vertices with n >= 5k - 1 and delta(G) >= n+k/2, then any nonspanning path system consisting of k paths, one of which has order four or greater, is extendable by one vertex. We then use this to show that for k >= 2 and n >= 5k-1, a graph on n vertices satisfying delta(G) >= n+2k-1/2 is pan-k-linked. In both cases, the minimum degree result is shown to be best possible. (C) 2008 Elsevier B.V. All rights reserved.