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) \geq 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) \geq 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\).