我们将一个$c$部竞赛图划分为若干$c$阶子竞赛图,若每个子竞赛图都是强连通的,则称该划分为强划分。强划分数$ST (r)$定义为最小的整数$c'$,使得对所有$c\geq c'$,每个正则的$r$-平衡$c$部竞赛图都存在一个强划分。Figueroa,Montellano-Ballesteros和Olsen证明了对于所有$r\geq 2$,$ST (r)$的存在性,并给出$5\leq ST (2)\leq 7$。本文中,我们确定$ST (2)=6$,并给出唯一一个不存在强划分的$2$-平衡$5$部竞赛图。
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.
[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.
北大中文核心期刊