A graph minor condition for graphs to be k-linked

A graph is called k-linked, if for any 2k distinct vertices x(1), x(2), ... , x(k), y(1), y(2), . . . , y(k), there exist k vertex disjoint paths P-1, P-2, . . . , P-k such that Pi connects x(i) and y(i) for each 1 <= i <= k. Robertson and Seymour showed that every 2k-connected graph having K3k as a minor is k-linked. In 2005, Chen, Gould, Kawarabayashi, Pfender, and Wei proved that every 6-connected graph having K-9(-) as a minor is 3-linked, where K-k(-i) is the graph obtained from the complete graph with k vertices by deleting exactly i edges. We improve these two results by showing that every 2kconnected graph having the graph obtained from K-3k by deleting independent k edges as a minor is k-linked.(c) 2023 Elsevier Ltd. All rights reserved.

Automated summary

This paper discusses the definition and properties of k-linked graphs and refers to previous research results. It improves these results by considering the graph obtained from deleting edges as a minor.