We call a partition of a $c$-partite tournament into tournaments of order $c$ strong if each tournament is strongly connected. The strong partition number, denoted as $ST(r)$, represents the minimum integer $c'$ such that every regular $r$-balanced $c$-partite tournament has a strong partition for all $c \geq c'$. Figueroa, Montellano-Ballesteros, and Olsen showed the existence of $ST(r)$ for all $r\geq 2$ and proved that $5\leq ST(2)\leq 7$. In this note, we establish that $ST(2)=6$ and we also show the unique $2$-balanced $5$-partite tournament which has no strong partition.
AI Jiangdong
,
HE Fankang
,
LIU Yihang
. Solution to strong partition of 2-balanced regular multipartite tournaments[J]. Operations Research Transactions, 2026
, 30(2)
: 45
-57
.
DOI: 10.15960/j.cnki.issn.1007-6093.2026.02.003
[1] Bang-Jensen J, Gutin G. Digraphs: Theory, Algorithms and Applications [M]. London: Springer-Verlag, 2009.
[2] Bang-Jensen J, Cohen N, Havet F. Finding good 2-partitions of digraphs II. Enumerable properties [J]. Theoretical Computer Science, 2016, 640: 1-19.
[3] Reid K B. Two complementary circuits in two-connected tournaments [M]//Alspach B R, Godsil C D. (eds.) North-Holland Mathematics Studies. Amsterdam: North-Holland, 1985, 115: 321-334.
[4] Volkmann L. Multipartite tournaments: A survey [J]. Discrete Mathematics, 2007, 307(24): 3097-3129.
[5] Volkmann L, Winzen S. Strong subtournaments containing a given vertex in regular multipartite tournaments [J]. Discrete Mathematics, 2008, 308(23): 5516-5521.
[6] Xu G, Li S, Li H, Guo Q. Strong subtournaments of order c containing a given vertex in regular c-partite tournaments with c ≥ 16[J]. Discrete Mathematics, 2011, 311(20): 2272-2275.
[7] Figueroa A P, Montellano-Ballesteros J J, Olsen M. Partition of regular balanced c-tournaments into strongly connected c-tournaments [J]. Discrete Mathematics, 2023, 346(7): 113459.
