Linkages and removable paths avoiding vertices.

A graph G is (2 , m) -linked if, for any distinct vertices a 1 , ... , a m , b 1 , b 2 in G , there exist disjoint connected subgraphs A , B of G such that a 1 , ... , a m ∈ V (A) and b 1 , b 2 ∈ V (B). A fundamental result in structural graph theory is the characterization of (2 , 2) -linked graphs. It appears to be difficult to characterize (2 , m) -linked graphs for m ≥ 3. In this paper, we provide a partial characterization of (2 , m) -linked graphs. This implies that every (2 m + 2) -connected graphs G is (2 , m) -linked and for any distinct vertices a 1 , ... , a m , b 1 , b 2 of G , there is a path P in G between b 1 and b 2 and avoiding { a 1 , ... , a m } such that G − P is connected, improving a previous connectivity bound of 10 m. [ABSTRACT FROM AUTHOR]