Every (13k − 6)-strong tournament with minimum out-degree at least 28k − 13 is k-linked

A digraph D is k-linked if it satisfies that for every choice of disjoint sets {x1,…,xk} and {y1,…,yk} of vertices of D there are vertex disjoint paths P1,…,Pk such that Pi is an (xi,yi)-path. Confirming a conjecture by Kühn et al., Pokrovskiy proved in 2015 that every 452k-strong tournament is k-li...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2022-06, Vol.345 (6), p.112831, Article 112831
Main Authors: Bang-Jensen, Jørgen, Skov Johansen, Kasper
Format: Article
Language:English
Subjects:
Connectivity
Linkage
Tournament
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A digraph D is k-linked if it satisfies that for every choice of disjoint sets {x1,…,xk} and {y1,…,yk} of vertices of D there are vertex disjoint paths P1,…,Pk such that Pi is an (xi,yi)-path. Confirming a conjecture by Kühn et al., Pokrovskiy proved in 2015 that every 452k-strong tournament is k-linked and asked for a better linear bound. Very recently Meng et al. proved that every (40k−31)-strong tournament is k-linked. In this note we use an important lemma from their paper to give a short proof that every (13k−6)-strong tournament of minimum out-degree at least 28k−13 is k-linked.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2022.112831