Highly linked graphs (Q2563507)

A simple graph with at least \(2k\) vertices is called \(k\)-linked if for any choice \(s_1,\dots,s_k\), \(t_1,\dots,t_k\) of \(2k\) distinct vertices there are \(k\) vertex-disjoint paths \(p_1,\dots,p_k\) with \(p_i\) joining \(s_i\) to \(t_i\), \(1\leq i\leq k\). Here the authors prove that if the connectivity number of \(G\) is at least \(22k\) then \(G\) is \(k\)-linked, extending ideas of \textit{N. Robertson} and \textit{P. Seymour} [J. Comb. Theory, Ser. B 63, No. 1, 65-110 (1995; Zbl 0823.05038)] who showed that if \(\kappa (G)\geq 10k\sqrt{\log_2 k}\) then \(G\) is \(k\)-linked.