SOME NECESSARY CONDITIONS FOR SPLIT TOURNAMENTS  HAVING NO DISJOINT CYCLES OF DIFFERENT LENGTHS

Lê Như Hiền; Mai Thanh Hồng; Vũ Thị Tuyết Mai; Chu Thị Quyên; Lê Xuân Hùng

doi:10.34238/tnu-jst.11722

SOME NECESSARY CONDITIONS FOR SPLIT TOURNAMENTS HAVING NO DISJOINT CYCLES OF DIFFERENT LENGTHS

About this article

Received: 17/12/24 Revised: 06/03/25 Published: 07/03/25

Authors

1. Le Nhu Hien , Hanoi University of Industry
2. Mai Thanh Hong, Hanoi University of Industry
3. Vu Thi Tuyet Mai, Hanoi University of Industry
4. Chu Thi Quyen, Hanoi University of Industry
5. Le Xuan Hung, Hanoi University of Industry

Abstract

A split tournament is a digraph graph D = (V, A) with a partition such that D[K] is a tournament, D[K] have no arc and for every two vertices exactly one of the arcs (u,v) and (v,u) is in A. We will denote such a digraph by . The problem of studying the existence of disjoint cycles of different lengths in directed graphs was started in 1983 by C. Thomassen, and has so far yielded many profound and interesting results. In this paper, we will continue to study the existence of disjoint cycles of different lengths in new graphs, that is strong split tournaments with minimum out-degree 3. We prove some necessary conditions for such a class of split tournaments to have no disjoint cycles of different lengths. The main results in this paper are important initial contributions to finding a characterization for the class of strong split tournaments with minimum out-degree 3, have no disjoint cycles of different lengths.

Keywords

Tournament; Split tournament; Vertex-disjoint cycles; Strong digraph; Cycles of different lengths

Full Text:

PDF (Tiếng Việt)

References

[1] J. Bang-Jensen and G. Gutin, Digraphs. Theory, Algorithms and Applications, Springer, New York, 2001.

[2] C. Thomassen, “Disjoint cycles in digraphs,” Combinatorica, vol. 3, pp. 393 – 396, 1983.

[3] M. A. Henning and A. Yeo, “Vertex disjoint cycles of different length in digraphs,” SIAM J. Discrete Math., vol. 26, pp. 687 – 694, 2012.

[4] N. Lichiardopol, “Proof of a conjecture of Henning and Yeo on vertex-disjoint directed cycles,” SIAM J. Discrete Math., vol. 28, pp. 1618 – 1627, 2014.

[5] D. T. Ngo, “Tournaments and bipartite tournaments without vertex disjoint cycles of different lengths,” SIAM J. Discrete Math., vol. 35, no. 1, pp. 485 – 494, 2021.

[6] X. H. Le, D. H. Do, and D. T. Ngo, “Vertex-disjoint cycles of different lengths in multipartite tournaments,” Discrete Math., vol. 345, 2022, Art. no. 112819.

[7] X. H. Le and D. T. Ngo, “Vertex-Disjoint Cycles of Different Lengths in Local Tournaments,” Graphs and Combinatorics, vol. 39, no. 5, 2023, Art. no. 92.

[8] J. Bang-Jensen and F. Havet, “Tournaments and semicomplete digraphs,” in Classes of Directed Graphs, J. Bang-Jensen and F. Havet, eds., Springer, New York, 2018, pp. 35 – 124.

DOI: https://doi.org/10.34238/tnu-jst.11722

Refbacks

There are currently no refbacks.



Remember me