北大中文核心期刊
中国科学引文数据库（CSCD）来源期刊
中国科技核心期刊
入选数学领域高质量科技期刊
Scopus
EBSCO 

运筹学学报（中英文） ›› 2026, Vol. 30 ›› Issue (2): 45-57.doi: 10.15960/j.cnki.issn.1007-6093.2026.02.003

• • 上一篇    下一篇

2-平衡正则多部竞赛图的强划分解法

艾江东†, 贺凡康, 刘奕航   

  1. 南开大学数学科学学院, 天津 300071
  • 收稿日期:2025-11-25 发布日期:2026-06-12
  • 通讯作者: 艾江东 E-mail:jd@nankai.edu.cn
  • 基金资助:
    国家自然科学基金 (No. 12522117), 天津市科技计划项目 (No. 24JCQNJC01960)

Solution to strong partition of 2-balanced regular multipartite tournaments

AI Jiangdong†, HE Fankang, LIU Yihang   

  1. School of Mathematical Sciences, Nankai University, Tianjin 300071, China
  • Received:2025-11-25 Published:2026-06-12

PDF

5

摘要： 我们将一个$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$部竞赛图。

关键词: 多部竞赛图, 强划分, 控制

Abstract: 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.

Key words: multi-partite tournament, strong partition, control

中图分类号: