完全二部图的强子图连通度

Strong Subgraph Connectivity on Complete Bipartite Digraphs

摘要: 无向图G的广义k-连通度是在1985年由Hager引入的定义，这个概念后来又被人们推广到有向图中并提出了强子图k-连通度的定义。近年来，强子图k-连通度的研究在有向图上取得很多重要结果。在本文中，我们研究并给出了完全二部有向图上的强子图k-连通度的若干结果。

Abstract: The definition of generalized connectivity of undirected graph G was introduced by Hager in 1985. This concept was extended to directed graph and the definition of strong subgraph k-connectivity was proposed. In recent years, the study of strong subgraph k-connectivity has achieved many im-portant results on directed graphs. In this paper, we study this concept and give some results on the strong subgraph k-connectivity on complete bipartite digraphs.

1. 引言

无论是在组合学意义还是算法意义上，连通度都是其中最基础的概念之一，不同文献中使用的连通度符号都有差别，本文使用的是文献 [1] [2] 中相关术语和符号。图G的广义k-连通度 ${\kappa }_k\left(G\right)$ 的概念在1985年由Hager [3] 引入，是连通度的“路版本”定义的自然推广。给定图G和其中的一个顶点子集S (S中元素个数至少为2)，当G中的子树T满足 $S\subseteq V\left(T\right)$ 时，我们称这个树T为一个S-斯坦纳树，也可以简称其为S-树。当两个S-树 $T_1$ 和 $T_2$ 满足 $E\left(T_1\right)\cap E\left(T_2\right)=\varnothing$ 时，我们称 $T_1$ 和 $T_2$ 为弧不交的。当两个弧不交的S-树 $T_1$ 和 $T_2$ 满足 $V\left(T_1\right)\cap V\left(T_2\right)=S$ 时，我们称 $T_1$ 和 $T_2$ 为内部不交的。广义局部连通度 ${\kappa }_S\left(G\right)$ 定义为G中内部不交S-树的最大个数。进一步，我们定义广义k-连通度为

${\kappa }_k\left(G\right)=\min \left\{{\kappa }_S\left(G\right)|S\subseteq V\left(G\right),\left|S\right|=k\right\}$，

其中k满足 $2\le k\le n$。容易得出，当 $k=2$ 时， ${\kappa }_2\left(G\right)=\kappa \left(G\right)$。

类似的，我们可以定义 ${\lambda }_k\left(G\right)$ 为

${\lambda }_k\left(G\right)=\min \left\{{\lambda }_S\left(G\right)|S\subseteq V\left(G\right),\left|S\right|=k\right\}$，

其中 ${\lambda }_S\left(G\right)$ 为G中弧不交S-树的最大个数。

在无向图广义k-连通度的定义中，可以将“S-树”替换为“G中包含S的连通子图”(这里面的S-树本身也是G的一个连通子图)，将“连通”替换为“强连通”来定义有向图的“广义k-连通度”。令 $D=\left(V\left(D\right),A\left(D\right)\right)$，为一个n阶有向图，S是 $V\left(D\right)$ 中的一个k元顶点子集，其中 $2\le k\le n$。我们设 $D_1,\cdots ,D_p$ 为D中包含S的强子图，对于任意的 $D_i$ 和 $D_j$，若满足 $V\left(D_i\right)\cap V\left(D_j\right)=S$ 和 $A\left(D_i\right)\cap A\left(D_j\right)=\varnothing$，则称 $D_i$ 和 $D_j$ 为内部不交的S-强子图，其中 $1\le i\le j\le p$。将 ${\kappa }_S\left(D\right)$ 定义为G中包含的S-内部不交强子图的最大个数，进一步定义强子图k-连通度为

${\kappa }_k\left(D\right)=\min \left\{{\kappa }_S\left(D\right)|S\subseteq V\left(D\right),\left|S\right|=k\right\}$，

根据其定义可得，当D不是强连通图时， ${\kappa }_2\left(D\right)=0$。类似的，引入 ${\lambda }_S\left(D\right)$ 和 ${\lambda }_k\left(D\right)$ 的定义，其中 ${\lambda }_S\left(D\right)$ 定义为D中包含S-弧不交强子图的最大个数，定义强子图k-弧连通度为

${\lambda }_k\left(D\right)=\min \left\{{\lambda }_S\left(D\right)|S\subseteq V\left(D\right),\left|S\right|=k\right\}$。

若有向图D中任意一条弧xy都能够在图D中找出一条弧yx与之对应，则D被称为对称的有向图。给定一个无向图G，通过将G中的每条边替换成对应的两个方向的弧构成一个对称有向图D，我们称D是G的完全双定向。若G是一个完全二部图 $K_{a,b}$，则它对应的完全二部有向图记作 ${\stackrel{\leftrightarrow }{K}}_{a,b}$。

Li等在文献 [4] 中给出了完全二部图 $K_{a,b}$ 边不交生成树的值和 $K_{a,b}$ 的广义k连通度的值。Li和Mao在 [5] 中总结了广义连通度的诸多结果，在此基础上，Sun等在 [6] [7] 中给出了完全有向图的强子图连通度的界，证明了竞赛图和对称有向图在不同情况下的复杂度。令 $k\ge 2$ 且 $l\ge 2$，Sun等在文献 [7] 中通过用WEAK k-LINKAGE PROBLEM归约证明了能否判断 ${\lambda }_S\left(D\right)\ge l$ 是一个NPC问题，在文献 [8] 中通过用DIRECTED q-LINKAGE PROBLEM归约证明了能否判断 ${\kappa }_S\left(D\right)\ge l$ 也是一个NPC问题。在本文中，对于 $k=2,k=3$ 和 $k=a+b$，我们确定了 ${\kappa }_k\left({\stackrel{\leftrightarrow }{K}}_{a,b}\right)$ 的精确值(引理2.4，定理2.5和定理2.6)。

2. 主要结果

引理2.1. [7] 令D为一个n阶有向图，k为一个整数且 $k\ge 2$，则

${\lambda }_{k+1}\left(D\right)\le {\lambda }_k\left(D\right)\left(k\le n-1\right)$，

${\kappa }_k\left(D^{\prime }\right)\le {\kappa }_k\left(D\right)$， ${\lambda }_k\left(D^{\prime }\right)\le {\lambda }_k\left(D\right)$，

${\kappa }_k\left(D\right)\le {\lambda }_k\left(D\right)\le \min \left\{{\delta }^{+}\left(D\right),{\delta }^{-}\left(D\right)\right\}$，

其中 $D^{\prime }$ 是D的一个生成子有向图。

引理2.2. [6] 令D为一个n阶有向图，k为一个整数且 $k\ge 2$，则 $1\le {\lambda }_k\left(D\right)\le n-1$， $1\le {\kappa }_k\left(D\right)\le n-1$，上界是可达的当且仅当 $D\cong \stackrel{\leftrightarrow }{K}$。

引理2.3. [9] [10] 完全S部有向图 ${\stackrel{\leftrightarrow }{K}}_{r,r,\cdots ,r}$ (s次)可以被分解成s个哈密顿圈当且仅当 $\left(r,s\right)\ne \left(4,1\right)$ 或 $\left(r,s\right)\ne \left(6,1\right)$。

引理2.4. [11] 对于任意给定的两个正整数a和b，其中 $a\le b$，我们有 ${\lambda }_k\left({\stackrel{\leftrightarrow }{K}}_{a,b}\right)=a\left(2\le k\le a+b\right)$。

定理2.5. 对于任意给定的两个正整数a和b，其中 $a\le b$，我们有 ${\kappa }_{a+b}\left({\stackrel{\leftrightarrow }{K}}_{a,b}\right)=a$。

证明：令 $D\cong {\stackrel{\leftrightarrow }{K}}_{a,b}$，在D中找到一个k元顶点子集S，其中 $\left|S\right|=a+b$。将 $V\left(D\right)$ 划分为 $V_1$ 和 $V_2$ 两个子集，其中 $V_1=\left\{u_i|1\le i\le a\right\}$， $V_2=\left\{v_j|1\le j\le b\right\}$。根据引理2.3可以通过由 $\left\{u_i,v_j|1\le i,j\le a\right\}$ 导出的D的子图得到 $H_i,\left(1\le i\le a\right)$ 个哈密顿圈。对每个 $1\le i\le a$，存在一个 $D_i$， $D_i$ 是由 $H_i$ 加上弧集 $\left\{u_i{v}_j,v_j{u}_i|a+1\le j\le b\right\}$ 所构成的D的强生成子图。此时对于任意的一对强子图 $D_i,D_j\left(1\le i\le j\le a\right)$，都有 $V\left(D_i\right)\cap V\left(D_j\right)=S$ 成立。再根据引理2.4： ${\lambda }_{a+b}\left(D\right)=a$，可以知道图D中任意a个强子图都是弧不交的，意味着D中至少有a个内部不交的S-强子图，即 ${\kappa }_{a+b}\left(D\right)\ge a$。再根据引理2.1我们能够得到这样一个事实： ${\kappa }_{a+b}\left(D\right)\le {\lambda }_{a+b}\left(D\right)\le \min \left\{{\delta }^{+}\left(D\right),{\delta }^{-}\left(D\right)\right\}=a$。综上所述，可以得到 ${\kappa }_{a+b}\left({\stackrel{\leftrightarrow }{K}}_{a,b}\right)=a$。定理得证。¨

定理2.6. 对于任意给定的两个正整数a和b，其中 $a\le b$，我们有 ${\kappa }_2\left({\stackrel{\leftrightarrow }{K}}_{a,b}\right)=a$。

证明：令 $D\cong {\stackrel{\leftrightarrow }{K}}_{a,b}$，将 $V\left(D\right)$ 根据两个独立集划分为 $V_1$ 和 $V_2$ 两个子集，其中 $V_1=\left\{u_i|1\le i\le a\right\}$， $V_2=\left\{v_j|1\le j\le b\right\}$。根据引理2.1，我们有 $\kappa \left(D\right)\le \lambda \left(D\right)\le \min \left\{{\delta }^{+}\left(D\right),{\delta }^{-}\left(D\right)\right\}=a$，下面只需在D中找至少a个内部不交的S-强子图。令 $S=\left\{x,y\right\}\subseteq V_1\cup V_2$，给定a个S-强子图 $D_i$，假设每个 $D_i\left(i\in \left\{1,2,\cdots ,a\right\}\right)$ 中都包含S。根据 $x,y$ 在顶点子集中的分布情况，分为以下两种情形进行讨论：

情形1： $x,y$ 属于同一个顶点子集，即 $\left\{x,y\right\}\subseteq V_1$ 或 $\left\{x,y\right\}\subseteq V_2$。不失一般性，假设 $x=u_1$， $y=u_2$。对于每一个 $i\in \left\{1,2,\cdots ,a\right\}$，令 $D_i$ 的顶点集为 $\text{V}\left(D_i\right)=\left\{u_1,u_2,v_i\right\}$，弧集为 $\text{A}\left(D_i\right)=\left\{u_1{v}_i,v_i{u}_1,u_2{v}_i,v_i{u}_2\right\}$。显然D中有a个内部不交的S-强子图。

情形2： $x,y$ 属于不同的顶点子集，即 $x\subseteq V_1,y\subseteq V_2$ 或 $x\subseteq V_2,y\subseteq V_1$。不失一般性，我们假设 $x=u_1$， $y=v_1$。令 $D_1$ 包含顶点 $x,y$ 和边 $u_1{v}_1,v_1{u}_1$。对于任意的 $i\in \left\{2,\cdots ,a\right\}$，令 $D_i$ 的顶点集为 $\text{V}\left(D_i\right)=\left\{u_1,v_1,u_i,v_i\right\}$，弧集为 $\text{A}\left(D_i\right)=\left\{u_1{v}_i,v_i{u}_i,u_i{v}_1,v_1{u}_i,u_i{v}_i,v_i{u}_1\right\}$。同样可以在D中找到a个内部不交的S-强子图。

在两种情况中找出内部不交的S-强子图最小值可以得到 ${\kappa }_2\left(D\right)=a$。定理得证。¨

进一步的，当 $k=3$ 时能够得到下列定理。

定理2.7. 对于任意给定的两个正整数a和b，其中 $3<a\le b$，我们有 ${\kappa }_3\left({\stackrel{\leftrightarrow }{K}}_{a,b}\right)=a-1$。

证明：令 $D\cong {\stackrel{\leftrightarrow }{K}}_{a,b}$，将 $V\left(D\right)$ 根据两个独立集划分为 $V_1$ 和 $V_2$ 两个子集，其中 $V_1=\left\{u_i|1\le i\le a\right\}$， $V_2=\left\{v_j|1\le j\le b\right\}$。根据引理2.1，我们有 ${\kappa }_3\left(D\right)\le {\lambda }_3\left(D\right)\le \min \left\{{\delta }^{+}\left(D\right),{\delta }^{-}\left(D\right)\right\}=a$，下面要在D中找到至少 $a-1$ 个内部不交的S-强子图。令 $S\subseteq V\left(D\right)$ 且 $\left|S\right|=3$，给定a个S-强子图 $D_i$，假设每个 $D_i\left(i\in \left\{1,2,\cdots ,a\right\}\right)$ 中都包含S。根据 $x,y$ 在顶点子集中的分布情况，分为以下两种情形进行讨论：

情形1：S中的顶点在同一个顶点子集中，即 $S\subseteq V_1$ 或 $S\subseteq V_2$。不失一般性，假设 $S=\left\{u_1,u_2,u_3\right\}$，对于每一个 $i\in \left\{1,2,\cdots ,a\right\}$， $D_i$ 为D中的一个S-强子图，其中 $D_i$ 的顶点集 $\text{V}\left(D_i\right)=\left\{u_1,u_2,u_3,v_i\right\}$，弧集 $\text{A}\left(D_i\right)=\left\{u_1{v}_i,v_i{u}_1,u_2{v}_i,v_i{u}_2,u_3{v}_i,v_i{u}_3\right\}$。容易得到D中存在a个所需的内部不交强子图 $D_i$。

情形2：S中的顶点不在同一个顶点子集中，不失一般性，进一步将其分成 $S=\left\{u_1,v_1,v_2\right\}$ 和 $S=\left\{u_1,u_2,v_1\right\}$ 两种情况来考虑。

情形2.1 当 $S=\left\{u_1,v_1,v_2\right\}$ 时， $D_1$ 的顶点集 $\text{V}\left(D_1\right)=\left\{u_1,v_1,v_2\right\}$，弧集 $\text{A}\left(D_1\right)=\left\{u_1{v}_1,v_1{u}_1,u_1{v}_2,v_2{u}_1\right\}$。对于剩下的每个 $i\in \left\{2,\cdots ,a\right\}$，令 $D_i$ 为顶点集 $\text{V}\left(D_i\right)=\left\{u_1,u_i,v_1,v_2,v_{i+1}\right\}$，弧集 $\text{A}\left(D_i\right)=\left\{u_1{v}_{i+1},v_{i+1}{u}_1,v_1{u}_i,u_i{v}_1,v_2{u}_i,u_i{v}_2,u_i{v}_{i+1},v_{i+1}{u}_i\right\}$ 的S-强子图。此时D中共有a个内部不交强子图 $D_i$ 符合所求。

情形2.2 当 $S=\left\{u_1,u_2,v_1\right\}$ 时，和情形2.1类似，但我们只能找到 $a-1$ 个内部不交强子图。假设D中有a个内部不交强子图 $D_i$，根据集合S包含的顶点，我们可以得到一个包含四条弧 $u_1{v}_1,v_1{u}_1,u_1{v}_2,v_2{u}_1$ 的S-强子图，设其为 $D_1$。为使每个强子图 $D_i\left(i\in \left\{1,2,\cdots ,a\right\}\right)$ 为内部不交的，对于任意 $i\ge 2$ 的强子图 $D_i$，令其顶点集为 $\left\{u_1,u_2,u_{i+1},v_1,v_i\right\}$，弧集为 $\left\{v_1{u}_{i+1},u_{i+1}{v}_1,u_{1}v,v_i{u}_1,u_2{v}_i,v_i{u}_2,v_i{u}_{i+1},u_{i+1}{v}_i\right\}$。此时顶点 $v_1$ 的度为 $2\left(a+1\right)$，与事实不符。因此D中只有 $a-1$ 个内部不交强子图。

综上所述，我们可以得到 ${\kappa }_3\left(D\right)=\min \left\{{\kappa }_S\left(D\right)|S\subseteq V\left(D\right),\left|S\right|=3\right\}=a-1$。¨

通过引理2.1和引理2.2可以得到 ${\kappa }_k\left({\stackrel{\leftrightarrow }{K}}_{a,b}\right)$ 的界，由定理2.5和定理2.5可以得到上界是紧的。

推论2.8. 对于任意给定的完全有向二部图 ${\stackrel{\leftrightarrow }{K}}_{a,b}$ 满足 $1\le {\kappa }_k\left({\stackrel{\leftrightarrow }{K}}_{a,b}\right)\le a$ ( $2\le k\le a+b$ )，当 $k=2$ 或 $k=a+b$ 时上界是可达的。

3. 总结和展望

本文找出了任意完全有向二部图 ${\stackrel{\leftrightarrow }{K}}_{a,b}$ 的界，确定了 $k=2,k=3$ 和 $k=a+b$ 时 ${\kappa }_k\left({\stackrel{\leftrightarrow }{K}}_{a,b}\right)$ 的精确值。进一步，我们还可以研究若给出其他k值是否能够计算相应 ${\kappa }_k\left({\stackrel{\leftrightarrow }{K}}_{a,b}\right)$ 的精确值，同时考虑在此情况下能否找出 ${\stackrel{\leftrightarrow }{K}}_{a,b}$ 更紧的下界。如果无法计算 ${\kappa }_k\left({\stackrel{\leftrightarrow }{K}}_{a,b}\right)$ 的精确值，我们可以考虑是否能够找出一个算法证明其是多项式时间内可解的问题。