On Sufficient Degree Conditions for a Graph to be $k$-linked
Ken‐ichi Kawarabayashi, Alexandr V. Kostochka, Gexin Yu · Combinatorics Probability Computing · 2006
A graph is $k$ -linked if for every list of $2k$ vertices $\{s_1,{\ldots}\,s_k, t_1,{\ldots}\,t_k\}$ , there exist internally disjoint paths $P_1,{\ldots}\, P_k$ such that each $P_i$ is an $s_i,t_i$ -path. We consider degree conditions and connectivity conditions sufficient to force a graph to be $k$ -linked. Let $D(n,k)$ be the minimum positive integer $d$ such that every $n$ -vertex graph with minimum degree at least $d$ is $k$ -linked and let $R(n,k)$ be the minimum positive integer $r$ such that every $n$ -vertex graph in which the sum of degrees of each pair of non-adjacent vertices is at least $r$ is $k$ -linked. The main result of the paper is finding the exact values of $D(n,k)$ and $R(n,k)$ for every $n$ and $k$ . Thomas and Wollan [14] used the bound $D(n,k)\leq (n+3k)/2-2$ to give sufficient conditions for a graph to be $k$ -linked in terms of connectivity. Our bound allows us to modify the Thomas–Wollan proof slightly to show that every $2k$ -connected graph with average degree at least $12k$ is $k$ -linked.