Vertex-disjoint cycles of different lengths in multipartite tournaments (Q2124611)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Vertex-disjoint cycles of different lengths in multipartite tournaments |
scientific article |
Statements
Vertex-disjoint cycles of different lengths in multipartite tournaments (English)
0 references
11 April 2022
0 references
An oriented graph is a digraph with no cycle of length \(2\). A multipartite tournament or \(k\)-partite tournament with \(k\geq 2\) is an oriented graph \(D=(V,A)\) with a partition \(V=V_1\cup V_2\cup\dots \cup V_k\) such that there are no arcs in the subdigraphs \(D[V1],D[V2],\dots,D[Vk]\) and for every two vertices \(u\in V_i\) and \(v\in V_j\) with \(i,j\in \{1,2,\dots,k\}\) and \(i\neq j\) exactly one of the arcs \(uv\) and \(vu\) is in \(A\). The sets \(V_1,V_2,\dots,V_k\) are called parts of the partition \(V =V_1 \cup V_2 \cup\dots\cup V_k\) of the \(k\)-partite tournament \(D\). \textit{M. A. Henning} and \textit{A. Yeo} [SIAM J. Discrete Math. 26, No. 2, 687--694 (2012; Zbl 1248.05079)] have given an example of a \(3\)-regular digraph having no disjoint cycles of different lengths. This digraph is denoted by \(D^3_8\) and a \(3\)-regular digraph having no disjoint cycles of different lengths has been given in [\textit{M. Abreu} et al., J. Comb. Theory, Ser. B 92, No. 2, 395--404 (2004; Zbl 1056.05109)] and it is denoted by \(D^3_7\). A digraph \(D = (V , A)\) is called strong if for every pair \(x, y\) of distinct vertices in \(D\), there exist both a path from \(x\) to \(y\) and a path from \(y\) to \(x\). The main result of this paper is as follows Every strong \(k\)-partite tournament \(D = (V , A)\) with \(k \geq 3\) and minimum out-degree \(3\), except the digraphs \(D^3_7\) and \(D^3_8\), contains two disjoint cycles of different lengths.
0 references
strong digraph
0 references
\(k\)-partite tournament
0 references
vertex-disjoint cycles
0 references
cycles of different lengths
0 references
0 references