2023/11/07 by Bin Chen, Chen, Bin, Xinmin Hou +5
Computer Science · #05C20 #05C38 #05C40 #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Distributed systems and fault tolerance #FOS: Mathematics #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2311.04068
openalex publication_date 2023/11/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A digraph D is k-linked if for any pair of two disjoint sets \x1,x2,…,xk\ and \y1,y2,…,yk\ of vertices in D, there exist vertex disjoint dipaths P1,P2,…,Pk such that Pi is a dipath from xi to yi for each i∈[k]. Pokrovskiy (JCTB, 2015) confirmed a conjecture of Kühn et al. (Proc. Lond. Math. Soc., 2014) by verifying that every 452k-connected tournament is k-linked. Meng et al. (Eur. J. Comb., 2021) improved this upper bound by showing that any (40k-31)-connected tournament is k-linked. In this paper, we show a better upper bound by proving that every \lceil 12.5k-6\rceil-connected tournament with minimum out-degree at least 21k-14 is k-linked. Furthermore, we improve a key lemma that was first introduced by Pokrovskiy (JCTB, 2015) and later enhanced by Meng et al. (Eur. J. Comb., 2021).