张新鸿, 王睿阳, 李堯楠, 李瑞娟
设 $D$ 是一个定向图, $X\subseteq V(D)$. 若在 $D$中将两个端点均属于 $X$ 的所有弧反向后得到一个新图, 则称此图为 $D$中 $X$ 的反转. $D$ 的反转数是通过依次反转顶点子集 $ X_1, \dots,X_k$ 而将 $D$ 变为一个无圈定向图所需的最小正整数 $k$, 记为inv(D). 设 $G$ 是一个无向图, $Y\subseteq V(G)$. 若在$G$ 中用 $\overline{G[Y]}$ 替换 $G[Y]$ 得到一个新图, 则称此图为$G$ 关于 $Y$ 的子图补. 在 $G$ 中依次对顶点子集 $Y_1, \dots,Y_l$ 做子图补运算而将 $G$ 变成一个空图所需的最小正整数 $l$ 称为$G$ 的子图补数, 记为 $c_2(G)$.本文通过建立反转数与子图补数之间的关系, 给出了某类条件下 $k$个竞赛图与 $s$ 个定向图的连图反转数的一个上界, 以及一类$k$-连定向图反转数的一个下界, 由此推广了 Behague 等人在解决Bang-Jensen 等人和 Aubian 等人提出的两个问题中所做的工作.