On the k-linkage problem for generalizations of semicomplete digraphs

A directed graph (digraph) D is k-linked if |D|≥2k, and for any 2k distinct vertices x₁,…,x_k,y₁,…,y_k of D, there exist vertex-disjoint paths P₁,…,P_k such that P_i is a path from x_i to y_i for each i∈[k]. In 1980, Thomassen conjectured that there exists a function f(k) such that every f(k)-strong digraph is k-linked. He later disproved this conjecture by showing that f(2) does not exist for general digraphs and proved that the function f(k) exists for the class of tournaments. In this paper we consider a large class D of digraphs which includes all semicomplete digraphs (digraphs with no pair of non-adjacent vertices) and all quasi-transitive digraphs (a digraph D is quasi-transitive if for any three vertices x,y,z of D, whenever xy and yz are arcs, then x and z are adjacent). We prove that every 3k-strong digraph D∈D with minimum out-degree at least 23k is k-linked. A digraph D is l-quasi-transitive if whenever there is a path of length l between vertices u and v in D the vertices u and v are adjacent. Hence 2-quasi-transitive digraphs are exactly the quasi-transitive digraphs. We prove that there is a function f(k,l) so that every f(k,l)-strong l-quasi-transitive digraph is k-linked. The main new tool in our proofs significantly strengthens an important property of vertices with maximum in-degree in a tournament. While Landau in 1953 already proved that such a vertex v is reachable by all other vertices by paths of length at most 2, we show that, in fact, the structure of these paths is much richer. In general there are many such paths for almost all out-neighbors of v and this property is crucial in our proofs.