Note on disjoint cycles in multipartite tournaments

Gregory Gutin; Wei Li; Shujing Wang; Anders Yeo; Yacong Zhou

doi:10.1016/j.disc.2024.114126

Note on disjoint cycles in multipartite tournaments

Gregory Gutin, Wei Li, Shujing Wang^*, Anders Yeo, Yacong Zhou

^*Corresponding author for this work

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

Abstract

In 1981, Bermond and Thomassen conjectured that for any positive integer k, every digraph with minimum out-degree at least 2k−1 admits k vertex-disjoint directed cycles. In this short paper, we verify the Bermond-Thomassen conjecture for triangle-free multipartite tournaments and 3-partite tournaments. Furthermore, we characterize 3-partite tournaments with minimum out-degree at least 2k−1 (k≥2) such that in each set of k vertex-disjoint directed cycles, every cycle has the same length.

Original language	English
Article number	114126
Journal	Discrete Mathematics
Volume	347
Issue number	10
Number of pages	5
ISSN	0012-365X
DOIs	https://doi.org/10.1016/j.disc.2024.114126
Publication status	Published - Oct 2024

Keywords

Bermond-Thomassen conjecture
Disjoint cycles
Minimum out-degree
Multipartite tournaments

Documents & Links

10.1016/j.disc.2024.114126

SDU Link

Check access to the material in SDU Library's search engine

Cite this

@article{30ec2f42dd154a238e5aa4802c3b5375,

title = "Note on disjoint cycles in multipartite tournaments",

abstract = "In 1981, Bermond and Thomassen conjectured that for any positive integer k, every digraph with minimum out-degree at least 2k−1 admits k vertex-disjoint directed cycles. In this short paper, we verify the Bermond-Thomassen conjecture for triangle-free multipartite tournaments and 3-partite tournaments. Furthermore, we characterize 3-partite tournaments with minimum out-degree at least 2k−1 (k≥2) such that in each set of k vertex-disjoint directed cycles, every cycle has the same length.",

keywords = "Bermond-Thomassen conjecture, Disjoint cycles, Minimum out-degree, Multipartite tournaments",

author = "Gregory Gutin and Wei Li and Shujing Wang and Anders Yeo and Yacong Zhou",

year = "2024",

month = oct,

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

language = "English",

volume = "347",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "10",

}

TY - JOUR

T1 - Note on disjoint cycles in multipartite tournaments

AU - Gutin, Gregory

AU - Li, Wei

AU - Wang, Shujing

AU - Yeo, Anders

AU - Zhou, Yacong

PY - 2024/10

Y1 - 2024/10

N2 - In 1981, Bermond and Thomassen conjectured that for any positive integer k, every digraph with minimum out-degree at least 2k−1 admits k vertex-disjoint directed cycles. In this short paper, we verify the Bermond-Thomassen conjecture for triangle-free multipartite tournaments and 3-partite tournaments. Furthermore, we characterize 3-partite tournaments with minimum out-degree at least 2k−1 (k≥2) such that in each set of k vertex-disjoint directed cycles, every cycle has the same length.

AB - In 1981, Bermond and Thomassen conjectured that for any positive integer k, every digraph with minimum out-degree at least 2k−1 admits k vertex-disjoint directed cycles. In this short paper, we verify the Bermond-Thomassen conjecture for triangle-free multipartite tournaments and 3-partite tournaments. Furthermore, we characterize 3-partite tournaments with minimum out-degree at least 2k−1 (k≥2) such that in each set of k vertex-disjoint directed cycles, every cycle has the same length.

KW - Bermond-Thomassen conjecture

KW - Disjoint cycles

KW - Minimum out-degree

KW - Multipartite tournaments

U2 - 10.1016/j.disc.2024.114126

DO - 10.1016/j.disc.2024.114126

M3 - Journal article

AN - SCOPUS:85195660040

SN - 0012-365X

VL - 347

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 10

M1 - 114126

ER -

Note on disjoint cycles in multipartite tournaments

Abstract

Keywords

Documents & Links

SDU Link

Fingerprint

Cite this