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

^*Kontaktforfatter

Institut for Matematik og Datalogi

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › peer review

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

Originalsprog	Engelsk
Artikelnummer	112831
Tidsskrift	Discrete Mathematics
Vol/bind	345
Udgave nummer	6
Antal sider	4
ISSN	0012-365X
DOI	https://doi.org/10.1016/j.disc.2022.112831
Status	Udgivet - 2022

Bibliografisk note

Funding Information:
Research supported by the Independent Research Fund Denmark under grant number DFF 7014-00037B . This paper was written while the second author was a masters student at Department of Mathematics and Computer Science.

Funding Information:
Research supported by the Independent Research Fund Denmark under grant number DFF 7014-00037B. This paper was written while the second author was a masters student at Department of Mathematics and Computer Science.

Publisher Copyright:
© 2022 The Author(s)

Finansiering

Research supported by the Independent Research Fund Denmark under grant number DFF 7014-00037B . This paper was written while the second author was a masters student at Department of Mathematics and Computer Science. Research supported by the Independent Research Fund Denmark under grant number DFF 7014-00037B. This paper was written while the second author was a masters student at Department of Mathematics and Computer Science.

Dokumenter og links

10.1016/j.disc.2022.112831Licens: CC BY

Open Access VersionForlagets udgivne version, 204 KBLicens: CC BY

SDU link

Tjek adgangen til materialet i Syddansk Universitetsbiblioteks søgemaskine

Citationsformater

@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

Bibliografisk note

Finansiering

Dokumenter og links

SDU link

Fingeraftryk

Citationsformater

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