Distance Between Two $k$-Sets and Path-Systems Extendibility

Abstract

Given a simple graph $G$ on $n$ vertices, let ${\sigma }_2(G)$ be the minimum sum of the degrees of any two non-adjacent vertices. The graph $G$ is said to be connected if any two distinct vertices may be joined by a path. It is easy to see that if ${\sigma }_2(G)\ge n-1$ then $G$ is not only connected, but we can choose the connecting path to be of size at most two. Ore $[4]$ proved that if ${\sigma }_2(G)\ge n+1$ we may always choose this path to cover all the vertices of $G$. In this paper we extend these results to systems of vertex disjoint paths connecting two vertex $k$-sets of $G$.