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 18.12.2017, Revised 19.06.2018, Accepted 09.08.2018, doi: 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∈{3, 4,..., n}. Find a characterization of strong n-partite tournaments having exactly n-m+1 cycles of length m; (2) Let 3≤ m≤ n and n≥ 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≤ m≤ 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

Links:
PDF