DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

Q. Guo, W. Meng

Title:

On the $n$-partite tournaments with exactly $n-m+1$ cycles of length $m$

Source:

Discussiones Mathematicae Graph Theory

Received: 2017-12-18, Revised: 2018-06-19, Accepted: 2018-08-09, https://doi.org/10.7151/dmgt.2167

Abstract:

Gutin and Rafiey [Multipartite tournaments with small number of cycles, Australas J. Combin. 34 (2006) 17–21] raised the following two problems: (1) Let $m\in\{3, 4,\ldots, n\}$. Find a characterization of strong $n$-partite tournaments having exactly $n-m+1$ cycles of length $m$; (2) Let $3\leq m\leq n$ and $n\geq 4$. Are there strong $n$-partite tournaments, which are not themselves tournaments, with exactly $n-m+1$ cycles of length $m$ for two values of $m$? In this paper, we discuss the strong $n$-partite tournaments $D$ containing exactly $n-m+1$ cycles of length $m$ for $4\leq m\leq n-1$. We describe the substructure of such $D$ satisfying a given condition and we also show that, under this condition, the second problem has a negative answer.

Keywords:

multipartite tournaments, tournaments, cycles

PDF
Close