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

Jørgen Bang-Jensen; Kasper Skov Johansen

doi:10.1016/j.disc.2022.112831

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

Jørgen Bang-Jensen^*, Kasper Skov Johansen

^*Corresponding author for this work

Department of Mathematics and Computer Science

Research output: Contribution to journal › Journal article › Research › peer-review

51 Downloads (Pure)

Abstract

A digraph D is k-linked if it satisfies that for every choice of disjoint sets {x₁,…,x_k} and {y₁,…,y_k} of vertices of D there are vertex disjoint paths P₁,…,P_k such that P_i is an (x_i,y_i)-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.

Original language	English
Article number	112831
Journal	Discrete Mathematics
Volume	345
Issue number	6
Number of pages	4
ISSN	0012-365X
DOIs	https://doi.org/10.1016/j.disc.2022.112831
Publication status	Published - 2022

Bibliographical note

Publisher Copyright:
© 2022 The Author(s)

Keywords

Connectivity
Linkage
Tournament

Documents & Links

10.1016/j.disc.2022.112831Licence: CC BY

Open Access VersionFinal published version, 204 KBLicence: CC BY

Cite this

@article{812b6a72ce37466c8b0a14ae68606861,

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

abstract = "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{\"u}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.",

keywords = "Connectivity, Linkage, Tournament",

author = "J{\o}rgen Bang-Jensen and {Skov Johansen}, Kasper",

note = "Publisher Copyright: {\textcopyright} 2022 The Author(s)",

year = "2022",

doi = "10.1016/j.disc.2022.112831",

language = "English",

volume = "345",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "6",

}

TY - JOUR

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

AU - Bang-Jensen, Jørgen

AU - Skov Johansen, Kasper

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

KW - Connectivity

KW - Linkage

KW - Tournament

U2 - 10.1016/j.disc.2022.112831

DO - 10.1016/j.disc.2022.112831

M3 - Journal article

AN - SCOPUS:85123855283

SN - 0012-365X

VL - 345

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 6

M1 - 112831

ER -

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

Abstract

Bibliographical note

Keywords

Documents & Links

Fingerprint

Cite this

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