A characterization of rich \(c\)-partite \((c \geq 7)\) tournaments without \((c + 2)\)-cycles
type: Item
instance of: scholarly article
title: A characterization of rich \(c\)-partite \((c \geq 7)\) tournaments without \((c + 2)\)-cycles
author: Jie Zhang
author: Zhilan Wang
author: Jin Yan
published in: Discrete Mathematics and Theoretical Computer Science. DMTCS
publication date: 2024-09-06T00:00:00Z
review text: In this paper, the authors focus on a characterization problem concerning a special class of \(c\)-partite tournaments: orientations of complete \(c\)-partite graphs.\N\NA digraph \(D\) is strong if, for every pair \(x, y\) of distinct vertices in \(D\), there exists a path from \(x\) to \(y\) and a path from \(y\) to \(x\).\N\NA \(c\)-partite tournament is said to be rich if it is strong, with each partite set containing \(n\geq 2\) vertices (for \(n=1\), we get tournaments on \(c\) vertices). For \(c\geq 5\), the family of all rich \(c\)-partite tournaments is denote by \(\mathcal{D}\). A \(q\)-cycle is a cycle with \(q\) arcs. \N\NIn [J. Lond. Math. Soc., II. Ser. 14, 277--282 (1976; Zbl 0344.05124)], \textit{J. A. Bondy} asked whether every multipartite tournament of \(\mathcal{D}\) contains a \((c + 1)\)-cycle. This was answered in the negative by \textit{G. Gutin} [Vestsi Acad. Navuk BSSR Ser. Fiz.-Mat., 5, 105--106 (1984; Zbl 0556.05033)], and later \textit{Y. Guo} and \textit{L. Volkmann} [J. Combin. Theory Ser. B, 66, 140--145 (1996; Zbl 0837.05067)] provided a complete characterization of tournaments of \(\mathcal{D}\) that have no \((c+1)\)-cycles.\N\NThe previous problem can be generalized, so looking for a characterization of rich \(c\)-partite tournaments without \((c + k)\)-cycles for some \(k\geq 2\).\N\NThe authors solve the problem for \(c\geq 8\) and \(k=2\).\par\N\NThe condition \(c\geq 8\) might be not sharp, so the characterization of rich \(c\)-partite tournaments without \((c + 2)\)-cycles, and \(5\leq c\leq 7\) remains an open problem
reviewed by: Paolo Dulio
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 7908415
zbMATH Keywords: complete \(c\)-partite graph
zbMATH Keywords: cycle
zbMATH Keywords: multipartite tournament
zbMATH Keywords: path
zbMATH Keywords: strong digraph
MaRDI profile type: Publication
cites work: Note on the existence of directed (k + 1)-cycles in diconnected completek-partite digraphs
cites work: Generalizations of tournaments: A survey
cites work: Q4500916
cites work: Classes of Directed Graphs
cites work: Q3856672
cites work: Diconnected Orientations and a Conjecture of Las Vergnas
cites work: A complete solution of a problem of Bondy concerning multipartite tournaments
cites work: Q3220618
cites work: Multipartite tournaments: a survey
DOI: 10.46298/DMTCS.9732
description: scientific article; zbMATH DE number 7908415