若干有向卡氏积图类广义3-弧强连通度的精确值

Precise Values for the Generalized 3-Arc-Connectivity of Cartesian Product of Some Digraph Classes

摘要: 无向图G的广义k-边连通度的定义是1985年由Hager引入的，这个定义后来又被人们推广到有向图中，并相应定义了有向图中的广义k-弧强连通度。近年来，广义k-弧强连通度的研究得到了很多重要的结果。在本文中，我们给出了某些有向卡氏积图类的3-弧强连通度的精确值。

Abstract: The definition of generalized k-edge connectivity of undirected graph G was introduced by Hager in 1985. This concept was extended to directed graph and the definition of generalized k-arc- connectivity was proposed. In recent years, the study of generalized k-arc-connectivity has achieved many important results. In this paper, we give precise values for the generalized 3-arc-connectivity of Cartesian product of some digraph classes.

1. 引言

在未特别声明的情况下，本篇论文涉及到的图均指有限、无环的并且没有平行弧的简单有向图，未解释的符号及术语引自文献 [1] [2] 。

用 $V\left(D\right)$ 与 $A\left(D\right)$ 分别表示有向图D的顶点集与弧集，一个有向图D是对称的，如果它可以由将对应的无向底图的边替换为两个相反方向的弧得到，也即 $D=\stackrel{\leftrightarrow }{G}$ 。圈有向图有两种，若在有向图D中，对D中每对不同的顶点x的和y，xy或者yx在图D的弧集里，这样的具有n个顶点的圈有向图记为 $\stackrel{\to }{C_n}$ 。若在有向图D中，对D中每对不同的顶点x的和y，xy和yx均在图D的弧集里，这样的具有m个顶点的圈有向图记为 $\stackrel{\leftrightarrow }{C_m}$ 。

无向图 $G=\left(V,E\right)$ 的广义k-连通度 ${\kappa }_k\left(G\right)$ 的概念由Hager [3] 于1985年引入 $\left(2\le k\le \left|V\right|\right)$ 。给定图G及其顶点子集 $S\subseteq V$ (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$ 并且 $V\left(T_1\right)\cap V\left(T_2\right)=S$ 时，我们称 $T_1$ 和 $T_2$ 为内部不交的。广义局部连通度 ${\kappa }_S\left(G\right)$ [3] 定义为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$ 。当两个S-树 $T_1$ 和 $T_2$ 满足 $E\left(T_1\right)\cap E\left(T_2\right)=\varnothing$ 时，我们称 $T_1$ 和 $T_2$ 为弧不交的。类似的，广义局部边连通度 ${\lambda }_S\left(G\right)$ 定义为G中边不交S-树的最大个数。相应的，我们定义 ${\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-树的最大个数 [4] 。其他有关无向图树连通度的结果可参考 [5] 。

为了将广义连通度的概念推广到有向图上，Sun和Yeo引入了有向图的树连通度的概念 [6] ，给定是n阶有向图 $D=\left(V\left(D\right),A\left(D\right)\right)$ 及其k元顶点子集S ( $2\le k\le n$ )且根节点 $r\in S$ 。一棵有向 $\left(S,r\right)$ -斯坦纳树或者简称为 $\left(S,r\right)$ -树T是一颗根节点在 $r\in S$ 并且 $S\subseteq V\left(T\right)$ 的外向树。两个 $\left(S,r\right)$ -树 $T_1$ 和 $T_2$ 被称为弧不相交的，若 $A\left(T_1\right)\cap A\left(T_2\right)=\varnothing$ 。两个弧不相交的 $\left(S,r\right)$ -树 $T_1$ 和 $T_2$ 被称为内部不相交，若 $V\left(T_1\right)\cap V\left(T_2\right)=S$ 。定义 ${\kappa }_{S,r}\left(D\right)$ 是D中内部不相交的 $\left(S,r\right)$ -树的最大数目。定义D的广义k-点强连通度为：

${\kappa }_k\left(D\right)=\min \left\{{\kappa }_{S,r}\left(D\right)|S\subseteq V,\left|S\right|=k,r\in S\right\}.$

作为k-边连通度的自然对应，Sun和Yeo [6] 引入了广义k-弧强连通度的概念。给定n阶有向图 $D=\left(V\left(D\right),A\left(D\right)\right)$ 及其k元顶点子集S ( $2\le k\le n$ )。定义 ${\lambda }_{S,r}\left(D\right)$ 为D中弧不相交的 $\left(S,r\right)$ -树的最大数目。D的广义k-弧强连通度定义为：

${\lambda }_k\left(D\right)=\min \left\{{\lambda }_{S,r}\left(D\right)|S\subseteq V\left(D\right),\left|S\right|=k,r\in S\right\}.$

关于有向图树连通度极值结果，Sun研究了有向图树连通度相关的极值问题 [7] ，给出了极小广义 $\left(k,\mathcal{l}\right)$ -点(弧)强连通有向图的定义：这类图的广义k-点(弧)强连通度至少为 $\mathcal{l}$ ，但去掉任意一条弧后，广义k-点(弧)强连通度至多为 $\mathcal{l}-1$ 。并且在某些情形下对极小广义 $\left(k,\mathcal{l}\right)$ -点(弧)强连通有向图分别进行了刻画。其他有关无向图树连通度的结果可参考综述文章 [8] 。

两个有向图G和H的卡氏积 $G\square H$ 是具有顶点集

$V\left(G\square H\right)=V\left(G\right)\times V\left(H\right)=\left\{\left(x,x^{\prime }\right)|x\in V\left(G\right),x^{\prime }\in V\left(H\right)\right\}$

和弧集

$A\left(G\square H\right)=\left\{\left(x,x^{\prime }\right)\left(y,y^{\prime }\right)|xy\in A\left(G\right),x^{\prime }=y^{\prime }或x=y,x^{\prime }{y}^{\prime }\in A\left(H\right)\right\}$

的有向图。

根据定义，我们可以证明G和H的卡氏积 $G\square H$ 是强连通的当且仅当G和H都是强连通的 [9] 。

令G和H是顶点集分别是 $V\left(G\right)=\left\{u_i|1\le i\le n\right\}$ 和 $V\left(H\right)=\left\{v_j|1\le j\le n\right\}$ 的有向图。我们用符号 $G\left(v_j\right)$ 来表示 $G\square H$ 中当 $1\le j\le m$ 时由顶点集 $\left\{\left(u_i,v_j\right)|1\le i\le n\right\}$ 生成的有向子图，并且用 $H\left(u_i\right)$ 来表示 $G\square H$ 中当 $1\le i\le n$ 时由顶点集 $\left\{\left(u_i,v_j\right)|1\le j\le m\right\}$ 生成的有向子图。容易看出， $G\left(v_j\right)\cong G$ 并且 $H\left(u_i\right)\cong H$ 。具体例子见下图1。

Figure 1. G, H Cartesian products

图1. G和H的卡氏积

2. 主要结果

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

${\lambda }_{k+1}\left(D\right)\le {\lambda }_k\left(D\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. 对于任意给定的两个正整数n和m，我们有 ${\lambda }_3\left(\stackrel{\to }{C_n}\square \stackrel{\to }{C_m}\right)=2$

证明：由引理2.1可知， ${\lambda }_3\left(\stackrel{\to }{C_n}\square \stackrel{\to }{C_m}\right)\le \min \left\{{\delta }^{+}\left(\stackrel{\to }{C_n}\square \stackrel{\to }{C_m}\right),{\delta }^{-}\left(\stackrel{\to }{C_n}\square \stackrel{\to }{C_m}\right)\right\}=2$ ，故只需在卡氏积图 $\stackrel{\to }{C_n}\square \stackrel{\to }{C_m}$ 找出2颗弧不交的 $\left(S,r\right)$ -树 $T_1$ 和 $T_2$ 即可。

令 $S=\left\{x,y,z\right\}$ ，根据 $x,y,z$ 在顶点子集中的分布情况，不难看出只需考虑 $x,y,z$ 当 $1\le i\le n,1\le j\le m$ 时分别在不同的 $\stackrel{\to }{C_n}\left(v_i\right)$ 和 $\stackrel{\to }{C_m}\left(v_j\right)$ 当中即可，其他的情形的讨论是类似的。不失一般性我们可以假设 $x=\left(u_1,v_1\right),y=\left(u_2,v_2\right),z=\left(u_3,v_3\right)$ 。由于 $\stackrel{\to }{C_n}$ 和 $\stackrel{\to }{C_m}$ 都是强连通的，故 $\stackrel{\to }{C_n}\square \stackrel{\to }{C_m}$ 也是强连通的，根据已知事实任意强连通有向图的任意顶点都能做外(内)分支的根点，故不失一般性我们可以设x为根点，如下图2所示，我们可以得到两颗包含S的弧不交的 $\left(S,x\right)$ -树 $T_1$ 和 $T_2$ ，它们的顶点集与弧集分别为：

$V\left(T_1\right)=\left\{x,y,z,\left(u_1,v_2\right),\left(u_2,v_3\right)\right\};A\left(T_1\right)=\left\{x\left(u_1,v_2\right),\left(u_1,v_2\right)y,y\left(u_2,v_3\right),\left(u_2,v_3\right)z\right\}.$

$V\left(T_2\right)=\left\{x,y,z,\left(u_2,v_1\right),\left(u_3,v_2\right)\right\};A\left(T_2\right)=\left\{x\left(u_2,v_1\right),\left(u_2,v_1\right)y,y\left(u_3,v_2\right),\left(u_3,v_2\right)z\right\}.$

Figure 2. $\stackrel{\to }{C_n}$ , $\stackrel{\to }{C_m}$ and their Cartesian products

图2. $\stackrel{\to }{C_n}$ 和 $\stackrel{\to }{C_m}$ 的卡氏积图

容易看出 $T_1$ 和 $T_2$ 是弧不交的。从而有

$2\le {\lambda }_3\left(\stackrel{\to }{C_n}\square \stackrel{\to }{C_m}\right)\le \min \left\{{\delta }^{+}\left(\stackrel{\to }{C_n}\square \stackrel{\to }{C_m}\right),{\delta }^{-}\left(\stackrel{\to }{C_n}\square \stackrel{\to }{C_m}\right)\right\}=2$

证毕。 ¨

定理2.3. 对于任意给定的两个正整数n和m，我们有 ${\lambda }_3\left(\stackrel{\to }{C_n}\square \stackrel{\leftrightarrow }{C_m}\right)=3$

Figure 3. $\stackrel{\to }{C_n}$ , $\stackrel{\leftrightarrow }{C_m}$ and their Cartesian products

图3. $\stackrel{\to }{C_n}$ 和 $\stackrel{\leftrightarrow }{C_m}$ 的卡氏积图

证明：由引理2.1可知， ${\lambda }_3\left(\stackrel{\to }{C_n}\square \stackrel{\leftrightarrow }{C_m}\right)\le \min \left\{{\delta }^{+}\left(\stackrel{\to }{C_n}\square \stackrel{\leftrightarrow }{C_m}\right),{\delta }^{-}\left(\stackrel{\to }{C_n}\square \stackrel{\leftrightarrow }{C_m}\right)\right\}=3$ ，故只需在卡氏积图 $\stackrel{\to }{C_n}\square \stackrel{\leftrightarrow }{C_m}$ 找出3颗弧不交的 $\left(S,r\right)$ -树 $T_1$ ， $T_2$ 和 $T_3$ 即可。

令 $S=\left\{x,y,z\right\}$ ，根据 $x,y,z$ 在顶点子集中的分布情况，不难看出只需考虑 $x,y,z$ 当 $1\le i\le n,1\le j\le m$ 时分别在不同的 $\stackrel{\to }{C_n}\left(v_i\right)$ 和 $\stackrel{\leftrightarrow }{C_m}\left(v_j\right)$ 当中即可，其他的情形的讨论是类似的。不失一般性我们可以假设 $x=\left(u_1,v_1\right),y=\left(u_2,v_2\right),z=\left(u_3,v_3\right)$ 。由于 $\stackrel{\to }{C_n}$ 和 $\stackrel{\leftrightarrow }{C_m}$ 都是强连通的，故 $\stackrel{\to }{C_n}\square \stackrel{\leftrightarrow }{C_m}$ 也是强连通的，根据已知事实任意强连通有向图的任意顶点都能做外(内)分支的根点，故不失一般性我们可以设x为根点，如上图3所示，我们可以得到3颗包含S的弧不交的 $\left(S,x\right)$ -树 $T_1$ ， $T_2$ 和 $T_3$ ，它们的顶点集与弧集分别为：

$V\left(T_1\right)=\left\{x,y,z,\left(u_1,v_2\right),\left(u_2,v_3\right)\right\};A\left(T_1\right)=\left\{x\left(u_1,v_2\right),\left(u_1,v_2\right)y,y\left(u_2,v_3\right),\left(u_2,v_3\right)z\right\}.$

$V\left(T_2\right)=\left\{x,y,z,\left(u_2,v_1\right),\left(u_3,v_2\right)\right\};A\left(T_2\right)=\left\{x\left(u_2,v_1\right),\left(u_2,v_1\right)y,y\left(u_3,v_2\right),\left(u_3,v_2\right)z\right\}.$

$V\left(T_3\right)=\left\{x,y,z,\left(u_1,v_{m-1}\right),\left(u_1,v_m\right),\left(u_2,v_m\right),\left(u_2,v_{m-1}\right),\cdot \cdot \cdot ,\left(u_2,v_3\right),\left(u_3,v_{m-1}\right),\left(u_3,v_{m-2}\right),\cdot \cdot \cdot ,\left(u_3,v_4\right)\right\}.$

$\begin{array}{c}A\left(T_3\right)=\{x\left(u_1,v_m\right),\left(u_1,v_m\right)\left(u_2,v_m\right),\left(u_2,v_m\right)\left(u_2,v_{m-1}\right),\cdot \cdot \cdot ,\left(u_2,v_3\right)y,\left(u_1,v_m\right)\left(u_1,v_{m-1}\right),\\ \left(u_1,v_{m-1}\right)\left(u_2,v_{m-1}\right),\left(u_2,v_{m-1}\right)\left(u_3,v_{m-1}\right),\left(u_3,v_{m-1}\right)\left(u_3,v_{m-2}\right),\cdot \cdot \cdot ,\left(u_3,v_4\right)z\}.\end{array}$

容易看出 $T_1$ ， $T_2$ 和 $T_3$ 是弧不交的。从而有

$3\le {\lambda }_3\left(\stackrel{\to }{C_n}\square \stackrel{\leftrightarrow }{C_m}\right)\le \min \left\{{\delta }^{+}\left(\stackrel{\to }{C_n}\square \stackrel{\leftrightarrow }{C_m}\right),{\delta }^{-}\left(\stackrel{\to }{C_n}\square \stackrel{\leftrightarrow }{C_m}\right)\right\}=3$

证毕。 ¨

定理2.4. 对于任意给定的两个正整数n和m，我们有 ${\lambda }_3\left(\stackrel{\leftrightarrow }{C_n}\square \stackrel{\leftrightarrow }{C_m}\right)=4$

Figure 4. $\stackrel{\leftrightarrow }{C_n}$ , $\stackrel{\leftrightarrow }{C_m}$ and their Cartesian products

图4. $\stackrel{\leftrightarrow }{C_n}$ 和 $\stackrel{\leftrightarrow }{C_m}$ 的卡氏积图

证明：由引理2.1可知， ${\lambda }_3\left(\stackrel{\leftrightarrow }{C_n}\square \stackrel{\leftrightarrow }{C_m}\right)\le \min \left\{{\delta }^{+}\left(\stackrel{\leftrightarrow }{C_n}\square \stackrel{\leftrightarrow }{C_m}\right),{\delta }^{-}\left(\stackrel{\leftrightarrow }{C_n}\square \stackrel{\leftrightarrow }{C_m}\right)\right\}=4$ ，故只需在卡氏积图 $\stackrel{\leftrightarrow }{C_n}\square \stackrel{\leftrightarrow }{C_m}$ 找出4颗弧不交的 $\left(S,r\right)$ -树 $T_1$ ， $T_2$ ， $T_3$ 和 $T_4$ 即可。

令 $S=\left\{x,y,z\right\}$ ，根据 $x,y,z$ 在顶点子集中的分布情况，不难看出只需考虑 $x,y,z$ 当 $1\le i\le n,1\le j\le m$ 时分别在不同的 $\stackrel{\leftrightarrow }{C_n}\left(v_i\right)$ 和 $\stackrel{\leftrightarrow }{C_m}\left(v_j\right)$ 当中即可，其他的情形的讨论是类似的。不失一般性我们可以假设 $x=\left(u_1,v_1\right),y=\left(u_2,v_2\right),z=\left(u_3,v_3\right)$ 。由于 $\stackrel{\leftrightarrow }{C_n}$ 和 $\stackrel{\leftrightarrow }{C_m}$ 都是强连通的，故 $\stackrel{\leftrightarrow }{C_n}\square \stackrel{\leftrightarrow }{C_m}$ 也是强连通的，根据已知事实任意强连通有向图的任意顶点都能做外(内)分支的根点，故不失一般性我们可以设x为根点，如上图4所示，我们可以得到4颗包含S的弧不交的 $\left(S,x\right)$ -树 $T_1$ ， $T_2$ ， $T_3$ 和 $T_4$ ，它们的顶点集与弧集分别为：

$V\left(T_1\right)=\left\{x,y,z,\left(u_1,v_2\right),\left(u_2,v_3\right)\right\};A\left(T_1\right)=\left\{x\left(u_1,v_2\right),\left(u_1,v_2\right)y,y\left(u_2,v_3\right),\left(u_2,v_3\right)z\right\}.$

$V\left(T_2\right)=\left\{x,y,z,\left(u_2,v_1\right),\left(u_3,v_2\right)\right\};A\left(T_2\right)=\left\{x\left(u_2,v_1\right),\left(u_2,v_1\right)y,y\left(u_3,v_2\right),\left(u_3,v_2\right)z\right\}.$

$V\left(T_3\right)=\left\{x,y,z,\left(u_1,v_{m-1}\right),\left(u_1,v_m\right),\left(u_2,v_m\right),\left(u_2,v_{m-1}\right),\cdots ,\left(u_2,v_3\right),\left(u_3,v_{m-1}\right),\left(u_3,v_{m-2}\right),\cdots ,\left(u_3,v_4\right)\right\}.$

$\begin{array}{l}A\left(T_3\right)=\{x\left(u_1,v_m\right),\left(u_1,v_m\right)\left(u_2,v_m\right),\left(u_2,v_m\right)\left(u_2,v_{m-1}\right),\cdots ,\left(u_2,v_3\right)y,\left(u_1,v_m\right)\left(u_1,v_{m-1}\right),\\ \left(u_1,v_{m-1}\right)\left(u_2,v_{m-1}\right),\left(u_2,v_{m-1}\right)\left(u_3,v_{m-1}\right),\left(u_3,v_{m-1}\right)\left(u_3,v_{m-2}\right),\cdots ,\left(u_3,v_4\right)z\}.\end{array}$

$\begin{array}{l}V\left(T_4\right)=\{x,y,z,\left(u_n,v_1\right),\left(u_n,v_2\right),\left(u_{n-1},v_2\right),\left(u_{n-2},v_2\right),\cdots ,\left(u_3,v_2\right),\left(u_n,v_m\right),\\ \left(u_{n-1},v_m\right),\cdots ,\left(u_3,v_m\right),\left(u_3,v_{m-1}\right),\cdots ,\left(u_3,v_4\right)\}.\end{array}$

$\begin{array}{l}A\left(T_4\right)=\{x\left(u_n,v_1\right),\left(u_n,v_1\right)\left(u_n,v_2\right),\left(u_n,v_2\right)\left(u_{n-1},v_2\right),\cdots ,\left(u_3,v_2\right)y,\left(u_n,v_1\right)\left(u_n,v_m\right),\\ \left(u_n,v_m\right)\left(u_{n-1},v_m\right),\cdots ,\left(u_4,v_m\right)\left(u_3,v_m\right),\left(u_3,v_m\right)\left(u_3,v_{m-1}\right),\cdots ,\left(u_3,v_4\right)z\}.\end{array}$

容易看出 $T_1$ ， $T_2$ ， $T_3$ 和 $T_4$ 是弧不交的。从而有

$4\le {\lambda }_3\left(\stackrel{\leftrightarrow }{C_n}\square \stackrel{\leftrightarrow }{C_m}\right)\le \min \left\{{\delta }^{+}\left(\stackrel{\leftrightarrow }{C_n}\square \stackrel{\leftrightarrow }{C_m}\right),{\delta }^{-}\left(\stackrel{\leftrightarrow }{C_n}\square \stackrel{\leftrightarrow }{C_m}\right)\right\}=4$

证毕。 ¨

3. 总结和展望

本文给出了若干有向卡氏积图类广义3-弧强连通度的精确值，即给出了 ${\lambda }_3\left(\stackrel{\to }{C_n}\square \stackrel{\to }{C_m}\right)=2$ ， ${\lambda }_3\left(\stackrel{\to }{C_n}\square \stackrel{\leftrightarrow }{C_m}\right)=3$ ， ${\lambda }_3\left(\stackrel{\leftrightarrow }{C_n}\square \stackrel{\leftrightarrow }{C_m}\right)=4$ 。进一步，我们还可以研究其他有向卡氏积图类广义3-弧强连通度精确值，同时考虑在此情况下能否同时给出这些有向卡氏积图类广义3-点强连通度的精确值，例如 ${\kappa }_3\left(\stackrel{\to }{C_n}\square \stackrel{\to }{C_m}\right)$ 的精确值。除此之外，还可以研究这些有向卡氏积图类广义k-弧强连通度 ${\lambda }_k\left(G\square H\right)$ 随着k取值不同的变化规律，是否能给出一个统一的取值公式。