完全图的笛卡尔积的广义3-连通度

The Generalized 3-Connectivity of Cartesian Product of Complete Graphs

摘要: 设S是图G中至少有2个顶点的集合，T是G的一棵子树。如果S⊆V(T)，则称T是G的一棵S-斯坦纳树。设T₁与T₂是S-斯坦纳树，如果E(T₁)∩E(T₂)=∅且V(T₁)∩V(T₂)=S，则称T₁与T₂是内部不交的S-斯坦纳树。K_G(S)表示图G中内部不交的S-斯坦纳树的最大数目，K_K(G)是当S遍及V(G)的所有k元子集时的最小的K_G(S)。在本文中，我们研究完全图的笛卡尔积的K₃-连通度。对于任意两个完全图K_n1与K_n2，确定K₃(K_n1,K_n2)=n₁+n₂-3；对于任意K(K≥2)个完全图，确定K3(K_n1,K_n2,...,K_nK)=∑_i=1^kn_i-K-1。

Abstract: Let S be a set of at least two vertices in a graph G. A subtree T of G is an S-Steiner tree if S⊆V(T). Two S-Steiner trees T₁ and T₂ are internally disjoint if E(T₁)∩E(T₂)=∅ and V(T₁)∩V(T₂)=S. Let K_G(S) be the maximum number of internally disjoint S-Steiner trees in G, and let K_K(G) be the minimum K_G(S) for S ranges over all k-subsets of V(G). In this paper, we study the K₃-connectivity of Cartesian product of complete graphs, determine K₃(K_n1,K_n2)=n₁+n₂-3 for any two complete graphs; K3(K_n1,K_n2,...,K_nK)=∑_i=1^kn_i-K-1 for any k complete graphs, where K≥2.

1. 引言

在本文中，所有的图都是无向、有限的简单图。对于在本文中没有提到的图论的概念与术语，我们可以参考 [1] 。

设图G是一个连通图，S是图G中至少有2个顶点的集合，T是G的一棵子树。如果 $S\subseteq V\left(T\right)$ ，则称T是G的一棵S-斯坦纳树。设 $T_1$ 与 $T_2$ 是S-斯坦纳树，如果 $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$ 是内部不交的S-斯坦纳树。对于 $V\left(G\right)$ 的一个子集S， ${\kappa }_G\left(S\right)$ 表示图G中内部不交的S-斯坦纳树的最大数目。如果 $S=\left\{x,y\right\}$ ，则 ${\kappa }_G\left(S\right)={\kappa }_G\left(\left\{x,y\right\}\right)$ 是局部点连通度。对于 $k\ge 2$ 的整数， ${\kappa }_k\left(G\right)$ 是当S遍及 $V\left(G\right)$ 的所有k元子集时的最小的 ${\kappa }_G\left(S\right)$ ，称它为广义k-连通度，简称 ${\kappa }_k$ -连通度。Chartrand等人 [2] 引入了 ${\kappa }_k$ -连通度。显然，当 $\left|S\right|=2$ 时， ${\kappa }_2\left(G\right)=\kappa \left(G\right)$ 。

笛卡尔积是最重要的图运算之一，并且在网络的设计与分析中有重要作用。在过去的几十年，许多图论学者研究了笛卡尔积图的(边)连通度 [3] - [9] 。显然，在同构意义下，该运算满足交换律，即 $G\square H\cong H\square G$ ，该运算满足结合律，即 $\left(F\square G\right)\square H\cong F\square \left(G\square H\right)$ 。

对于一般图G来说，确定 ${\kappa }_k\left(G\right)$ 是一件非常困难的事情。到目前为止，只有少数图类的 ${\kappa }_k$ -连通度被确定，例如，Chartrand等人 [10] 确定了完全图的 ${\kappa }_k$ -连通度；Lin和Zhang确定了超立方体的 ${\kappa }_4$ -连通度；Li和Wang [11] 确定了递归循环图的 ${\lambda }_3$ -连通度与 ${\kappa }_3$ -连通度，等等。图论学者研究了图的广义连通度的上界与下界 [12] [13] [14] [15] [16] ，图论学者研究了图运算的广义(边)连通度的上界与下界 [12] [17] 。更多的结果，可以参考 [18] 。

在本文中，我们将研究完全图的笛卡尔积的 ${\kappa }_3$ -连通度。本文的结构如下，在第2部分，我们将介绍一些定义和已知的结论；在第3部分，我们将给出主要的结果。

2. 预备知识

设G和H是两个图，图G与H的笛卡尔积，记作 $G\square H$ ，其顶点集为 $V\left(G\right)\times V\left(H\right)$ ，两个顶点 $\left(u,v\right)$ 与 $\left(u^{\prime },v^{\prime }\right)$ 相邻当且仅当 $u=u^{\prime }$ 且 $v{v}^{\prime }\in E\left(H\right)$ ，或 $v=v^{\prime }$ 且 $u{u}^{\prime }\in E\left(G\right)$ 。特别地，n条路的笛卡尔积是n-维网格图。长为1的n条路的笛卡尔积是n-维超立方体。

设G与H是两个图，顶点集分别为 $V\left(G\right)=\left\{u_1,u_2,\cdots ,u_n\right\}$ ， $V\left(H\right)=\left\{v_1,v_2,\cdots ,v_m\right\}$ 。我们用 $G\left(u_i,v_j\right)$ 来表示 $G\square H$ 的子图，这个子图是由顶点集 $\left\{\left(u_i,v_j\right)|1\le i\le n\right\}$ 诱导出来的。类似的，我们用 $H\left(u_i,v_j\right)$ 来表示 $G\square H$ 的子图，这个子图是由顶点集 $\left\{\left(u_i,v_j\right)|1\le j\le m\right\}$ 诱导出来的。显然，对于图G中的不同顶点 $u_{i_1}$ 与 $u_{i_2}$ ，有 $G\left(u_{i_1},v_j\right)=G\left(u_{i_2},v_j\right)$ 。为了简单，我们可以用 $G^{v_j}$ 来代替 $G\left(u_i,v_j\right)\left(1\le i\le n\right)$ 。类似的，我们也可以用 $H^{u_i}$ 来代替 $H\left(u_i,v_j\right)\left(1\le j\le m\right)$ 。下面的几个符号可以简化我们的证明。

给定一个顶点 $v_a\in V\left(H\right)$ ，对于 $V\left(G\right)$ 中的任意顶点u，有 $u^{v_a}:=\left(u,v_a\right)$ ，对于G中的任意子图 $G_1$ ，有 $G_1^{v_a}:=\left(V\left(G_1^{v_a}\right),E\left(G_1^{v_a}\right)\right)$ ，其中 $V\left(G_1^{v_a}\right)=\left\{\left(u,v_a\right):u\in V\left(G_1\right)\right\}$ ， $E\left(G_1^{v_a}\right)=\left\{\left(u,v_a\right)\left(u^{\prime },v_a\right):u{u}^{\prime }\in E\left(G_1\right)\right\}$ 。

给定一个顶点 $v_b\in V\left(H\right)$ ，对于任意顶点 $\left(u,v_a\right)\in V\left(G^{v_a}\right)$ ，有 ${\left(u,v_a\right)}^{v_b}:=\left(u,v_b\right)$ ，对于任意子图 $$ ，有 $G_1^{v_b}:=\left(V\left(G_1^{v_b}\right),E\left(G_1^{v_b}\right)\right)$ ，其中 $V\left(G_1^{v_b}\right)=\left\{\left(u,v_b\right):\left(u,v_a\right)\in V\left(G_1^{v_a}\right)\right\}$ ， $E\left(G_1^{v_b}\right)=\left\{\left(u,v_b\right)\left(u^{\prime },v_b\right):\left(u,v_a\right)\left(u^{\prime },v_a\right)\in E\left(G_1^{v_a}\right)\right\}$ 。

类似的，给定一个顶点 $u_a\in V\left(G\right)$ ，对于 $v\in V\left(H\right)$ 可以定义映射 $v^{u_a}$ ，对于 $H_1\subseteq H$ 可以定义映射 $H_1^{u_a}$ ；给定一个顶点 $u_b\in V\left(G\right)$ ，对于 $\left(u_a,v\right)\in V\left(H^{u_a}\right)$ 可以定义映射 ${\left(u_a,v\right)}^{u_b}$ ，对于 $H_1\subseteq H^{u_a}$ 可以定义映射 $H_1^{u_b}$ 。

下面的几个定理和引理对我们要证明的结果很重要。

定理2.1 [10] ：对于任意两个整数n和k， $2\le k\le n$ ，有 ${\kappa }_k\left(K_n\right)=n-\lceil \frac{k}{2}\rceil$ 。

引理2.2 [13] ：设图G是一个至少有3个顶点的连通图，如果图G有两个最小度为 $\delta \left(G\right)$ 的相邻顶点，则有 ${\kappa }_k\left(G\right)\le \delta \left(G\right)-1$ ；而且，上界是紧的。

定理2.3 [1] ：设图G是一个k-连通图，如果x与y是G中的一对不同顶点，那么在图G中存在k条内部不交的xy-路 $P_1,P_2,\cdots ,P_k$ 。

引理2.4 [19] ：如果图G是k-连通的，那么对于任意顶点x和子集 $U\subseteq V\left(G\right)\backslash x$ ，满足 $\left|U\right|\ge k$ ，都有一个大小为k的x，U-扇。

定理2.5 [20] ： ${\kappa }_4\left(Q_k\right)=k-1$ ， $k\ge 2$ 。

引理2.6 [20] ：设 $k,r$ 是两个整数， $k\ge 4$ ，G是一个r-正则图，如果 ${\kappa }_k\left(G\right)=r-1$ ，那么 ${\kappa }_{k-1}\left(G\right)=r-1$ 。

引理2.7 [17] ：设 $C_1,C_2,\cdots ,C_k$ 是k个圈，则 ${\kappa }_3\left(C_1\square C_2\square \cdots \square C_k\right)=2k-1$ 。

3. 主要定理及其证明

在本文中， $K_{n_i}$ 表示有 $n_i$ 个顶点的完全图，其中 $1\le i\le k$ 。一条xy-路是一条起始于x，终止于y的路。对于一条路P来说，其中 $x,y\in V\left(P\right)$ ，我们用 $xPy$ 去表示P上连接 $x,y$ 的子路。

定理3.1：对于任意两个完全图 $K_{n_1}$ 与 $K_{n_2}$ ，有 ${\kappa }_3\left(K_{n_1}\square K_{n_2}\right)=n_1+n_2-3$ 。

证明：根据 $n_1$ 与 $n_2$ 的取值情况，考虑如下三种情形。

情形1： $n_1=n_2=2$ 。

因为 $n_1=n_2=2$ ，所以两个完全图都是 $K_2$ 。显然， ${\kappa }_3\left(K_2\square K_2\right)={\kappa }_3\left(C_4\right)=1=2+2-3$ 。

情形2： $n_1\ge 3,n_2=2$ 。

由引理2.2知， ${\kappa }_3\left(K_{n_1}\square K_2\right)\le \delta \left(K_{n_1}\square K_2\right)-1=n_1-1$ ，故只需证 ${\kappa }_3\left(K_{n_1}\square K_2\right)\ge n_1-1$ 。令 $V\left(K_{n_1}\right)=\left\{u_1,u_2,\cdots ,u_{n_1}\right\}$ ， $V\left(K_2\right)=\left\{v_1,v_2\right\}$ ， $S=\left\{x,y,z\right\}\subseteq V\left(K_{n_1}\square K_2\right)$ 。下面分两种子情形讨论。

子情形2.1： $S\subseteq K_{n_1}^{v_i}$ ， $i=1,2$ 。

不失一般性，假设 $S\subseteq K_{n_1}^{v_1}$ 。由定理2.1知， $$ ，故在 $K_{n_1}$ 中有 $n_1-2$ 棵内部不交的S-斯坦纳树，记作 $T_1,T_2,\cdots ,T_{n_1-2}$ 。令 $T_{n_1-1}=T_1^{v_2}\cup x{x}^{v_2}\cup y{y}^{v_2}\cup z{z}^{v_2}$ 。显然， $T_1,T_2,\cdots ,T_{n_1-1}$ 是 $n_1-1$ 棵内部不交的S-斯坦纳树。

子情形2.2：S中的某两个顶点属于某个 $K_{n_1}^{v_i}$ ， $i=1,2$ 。

不失一般性，假设 $x,y\in K_{n_1}^{v_1}$ ， $z\in K_{n_1}^{v_2}$ 。因为 $\kappa \left(K_{n_1}\right)=n_1-1$ ， $K_{n_1}^{v_i}\cong K_{n_1}$ ， $i=1,2$ ，所以由定理2.3知，在 $K_{n_1}^{v_1}$ 中存在 $n_1-1$ 条内部不交的xy-路， $1\le i\le n_1-1$ ，在 $K_{n_1}^{v_2}$ 中存在 $n_1-1$ 条内部不交的 $x^{v_2}z$ -路 $Q_i$ ， $1\le i\le n_1-1$ 。令 $x_i$ 是在 $P_i$ 上的x的邻点。令 $T_i=P_i\cup x_i^{v_2}{Q}_{i}z\cup x_i^{v_2}{x}_i$ ， $1\le i\le n_1-1$ 。显然， $T_1,T_2,\cdots ,T_{n_1-1}$ 是 $n_1-1$ 棵内部不交的S-斯坦纳树。

情形3： $n_1\ge 3,n_2\ge 3$ 。

由引理2.2知， ${\kappa }_3\left(K_{n_1}\square K_{n_2}\right)\le \delta \left(K_{n_1}\square K_{n_2}\right)-1=n_1+n_2-3$ ，故只需证 ${\kappa }_3\left(K_{n_1}\square K_{n_2}\right)\ge n_1+n_2-3$ 。令 $V\left(K_{n_1}\right)=\left\{u_1,u_2,\cdots ,u_{n_1}\right\}$ ， $V\left(K_{n_2}\right)=\left\{v_1,v_2,\cdots ,v_{n_2}\right\}$ ， $S=\left\{x,y,z\right\}\subseteq V\left(K_{n_1}\square K_{n_2}\right)$ 。下面分三种子情形讨论。

子情形3.1： $S\subseteq K_{n_1}^{v_i}$ ， $1\le i\le n_2$ 。

因为此情形与子情形2.1的讨论类似，所以留给读者证明。

子情形3.2：S中的某两个顶点属于某个 $K_{n_1}^{v_i}$ ， $1\le i\le n_2$ 。

因为此情形与子情形2.2的讨论类似，所以留给读者证明。

子情形3.3：S中的三个顶点分别属于不同的 $K_{n_1}^{v_i}$ ， $1\le i\le n_2$ 。

不失一般性，设 $x\in K_{n_1}^{v_1}$ ， $y\in K_{n_1}^{v_2}$ ， $z\in K_{n_1}^{v_3}$ 。下面分三种情形讨论。

如果 $S\subseteq K_{n_2}^{u_i}$ ，不妨设 $S\subseteq K_{n_2}^{u_1}$ 。由定理2.1知， ${\kappa }_3\left(K_{n_2}^{u_1}\right)=n_2-2$ ，所以在 $K_{n_2}^{u_1}$ 中有 $n_2-2$ 棵内部不交的S-斯坦纳树，记作 $T_1,T_2,\cdots ,T_{n_2-2}$ 。令 ${T^{\prime }}_i=T_1^{u_i}\cup x{x}^{u_i}\cup y{y}^{u_i}\cup z{z}^{u_i}$ ， $2\le i\le n_1$ 。显然， $T_1,T_2,\cdots ,T_{n_2-2},{T^{\prime }}_2,\cdots ,{T^{\prime }}_{n_1}$ 是 $n_1+n_2-3$ 棵内部不交的S-斯坦纳树。

如果 $x,y\in K_{n_2}^{u_s}$ ， $z\in K_{n_2}^{u_t}$ , 其中 $s\ne t$ 。因为 $\kappa \left(K_{n_1}\right)=n_1-1$ ， $K_{n_1}^{v_1}\cong K_{n_1}$ ，所以由定理2.3知，在 $K_{n_1}^{v_1}$ 中存在 $n_1-1$ 条内部不交的 $x{z}^{v_1}$ -路 $P_i$ ， $1\le i\le n_1-1$ 。因为 $K_{n_1}$ 是简单图，所以在 $K_{n_1}^{v_1}$ 中可以找到 $n_1-2$ 条长度至少为2的 $x{z}^{v_1}$ -路 $P_i$ ， $1\le i\le n_1-2$ 。令 $x_i$ 是在 $P_i$ 上的x的邻点， $T_i=x{P}_i{x}_i\cup x_i^{v_2}{P}_i^{v_2}y\cup x_i^{v_3}{P}_i^{v_3}z\cup x_i^{v_2}{x}_i\cup x_i^{v_2}{x}_i^{v_3}$ ， $1\le i\le n_1-2$ ； $T_{n_1-1}=P_{n_1-1}\cup P_{n_1-1}^{v_2}\cup z^{v_1}{z}^{v_2}\cup z^{v_2}z$ ； $T_{n_1}=xy\cup y{y}^{v_3}\cup P_{n_1-1}^{v_3}$ ； ${T^{\prime }}_j=x^{v_j}x\cup x^{v_j}y\cup z^{v_j}z\cup P_1^{v_j}$ ， $4\le j\le n_2$ 。显然， $T_1,T_2,\cdots ,T_{n_1},{T^{\prime }}_4,\cdots ,{T^{\prime }}_{n_2}$ 是 $n_1+n_2-3$ 棵内部不交的S-斯坦纳树。

如果 $x\in K_{n_2}^{u_r}$ ， $y\in K_{n_2}^{u_s}$ ， $z\in K_{n_2}^{u_t}$ ，其中 $r,s,t$ 不相等。当 $n_1=n_2=3$ 时，由引理2.7知， ${\kappa }_3\left(K_3\square K_3\right)={\kappa }_3\left(C_3\square C_3\right)=3$ ，故定理成立。当 $n_1\ge 4$ 和 $n_2\ge 3$ 时，令 $w_i$ 是在图 $K_{n_1}^{v_1}$ 中除顶点 $y^{v_1}$ 与 $z^{v_1}$ 外的x的邻点，则 $T_i=x{w}_i\cup w_i{w}_i^{v_2}\cup w_i^{v_2}{w}_i^{v_3}\cup w_i^{v_2}y\cup w_i^{v_3}z$ ， $1\le i\le n_1-3$ 。令 ${T^{\prime }}_1=x{y}^{v_1}\cup y^{v_1}{z}^{v_1}\cup y{y}^{v_1}\cup z{z}^{v_1}$ ； ${T^{\prime }}_2=x{x}^{v_2}\cup x^{v_2}y\cup y{z}^{v_2}\cup z^{v_2}z$ ； ${T^{\prime }}_3=x{x}^{v_3}\cup x^{v_3}{y}^{v_3}\cup y^{v_3}z\cup y^{v_3}y$ ； ${T^{\prime }}_j=x{x}^{v_j}\cup y{y}^{v_j}\cup z{z}^{v_j}\cup x^{v_j}{y}^{v_j}\cup y^{v_j}{z}^{v_j}$ ， $4\le j\le n_2$ 。显然， $T_1,T_2,\cdots ,T_{n_1-3},{T^{\prime }}_1,\cdots ,{T^{\prime }}_{n_2}$ 是 $n_1+n_2-3$ 棵内部不交的S-斯坦纳树。

定理3.2：对于任意 $k\left(k\ge 2\right)$ 个完全图，有 ${\kappa }_3\left(K_{n_1}\square K_{n_2}\square \cdots \square K_{n_k}\right)={\displaystyle {\sum }_{i=1}^k{n}_i-k-1}$ 。

证明：对k用归纳法。因为图的笛卡尔积满足交换律和结合律，所以可设 $n_1\le n_2\le \cdots \le n_k$ 。如果 $n_k=2$ ，那么 $K_{n_1}\square K_{n_2}\square \cdots \square K_{n_k}$ 是超立方体 $Q_k$ ，由定理2.5与引理2.6知，定理成立。

接下来只讨论 $n_k\ge 3$ 即可。当 $k=2$ 时，由定理3.1知，定理成立；假设对于任意不超过 $k-1$ 个完全图的笛卡尔积，定理都成立，即 ${\kappa }_3\left(K_{n_1}\square K_{n_2}\square \cdots \square K_{n_{k-1}}\right)={\displaystyle {\sum }_{i=1}^{k-1}{n}_i}-k$ 成立；现在证明对于任意k个完全图的笛卡尔积，定理成立。由引理2.2知， ${\kappa }_3\left(K_{n_1}\square K_{n_2}\square \cdots \square K_{n_k}\right)\le \delta \left(K_{n_1}\square K_{n_2}\square \cdots \square K_{n_k}\right)-1={\displaystyle {\sum }_{i=1}^k{n}_i}-k-1$ ，故只需证 ${\kappa }_3\left(K_{n_1}\square K_{n_2}\square \cdots \square K_{n_k}\right)\ge {\displaystyle {\sum }_{i=1}^k{n}_i}-k-1$ 。为了简便，令图G表示图 $K_{n_1}\square K_{n_2}\square \cdots \square K_{n_{k-1}}$ ， $a={\displaystyle {\sum }_{i=1}^{k-1}{n}_i}-k$ ， $b={\displaystyle {\sum }_{i=1}^k{n}_i}-k-1$ 。令 $V\left(G\right)=\left\{u_1,u_2,\cdots ,u_n\right\}$ ， $V\left(K_{n_k}\right)=\left\{v_1,v_2,\cdots ,v_{n_k}\right\}$ ， $S=\left\{x,y,z\right\}\subseteq V\left(G\square K_{n_k}\right)$ 。考虑如下三种情形。

情形1： $S\subseteq G^{v_i}$ ， $1\le i\le n_k$ 。

不失一般性，假设 $S\subseteq G^{v_1}$ 。由归纳假设知，在 $G^{v_1}$ 中可以找到a棵内部不交的S-斯坦纳树，记作 $T_1,T_2,\cdots ,T_a$ 。我们只需在 $G^{v_1}$ 外找 $n_k-1$ 棵内部不交的S-斯坦纳树，令 ${T^{\prime }}_i=T_1^{v_i}\cup x{x}^{v_i}\cup y{y}^{v_i}\cup z{z}^{v_i}$ ， $2\le i\le n_k$ 。显然， $T_1,T_2,\cdots ,T_a,{T^{\prime }}_2,\cdots ,{T^{\prime }}_{n_k}$ 是b棵内部不交的S-斯坦纳树。

情形2：S中的某两个顶点属于某个 $G^{v_i}$ ， $1\le i\le n_k$ 。

不失一般性，假设 $x,y\in G^{v_1}$ ， $z\in G^{v_2}$ 。下面分两种子情形讨论。

子情形2.1： $\left|z^{v_1}\cap \left\{x,y\right\}\right|=0$ 。

因为 $\kappa \left(G\right)=\delta \left(G\right)=a+1$ ， $G^{v_i}\cong G$ ， $i=1,2,\cdots ,n_k$ ，所以由定理2.3知，在 $G^{v_1}$ 中存在 $a+1$ 条内部不交的xy-路 $P_i$ ， $1\le i\le a+1$ ，在 $G^{v_2}$ 中存在 $a+1$ 条内部不交的 $x^{v_2}z$ -路 $Q_i$ ， $1\le i\le a+1$ 。令 $x_i$ 是在 $P_i$ 上的x的邻点。在 $G^{v_j}$ 中任取一棵 $\left\{x^{v_j},y^{v_j},z^{v_j}\right\}$ -斯坦纳树 $R^{v_j}$ ， $3\le j\le n_k$ 。令 $T_i=P_i\cup x_i^{v_2}{Q}_{i}z\cup x_i^{v_2}{x}_i$ ， $1\le i\le a+1$ ； ${T^{\prime }}_j=R^{v_j}\cup x{x}^{v_j}\cup y{y}^{v_j}\cup z{z}^{v_j}$ ， $3\le j\le n_k$ 。显然， $T_1,T_2,\cdots ,T_{a+1},{T^{\prime }}_3,\cdots ,{T^{\prime }}_{n_k}$ 是b棵内部不交的S-斯坦纳树。

子情形2.2： $\left|z^{v_1}\cap \left\{x,y\right\}\right|=1$ 。

不失一般性，假设 $z^{v_1}=y$ 。因为 $\kappa \left(G\right)=\delta \left(G\right)=a+1$ ， $G^{v_1}\cong G$ ，所以由定理2.3知，在中存在 $a+1$ 条内部不交的xy-路 $P_i$ ， $1\le i\le a+1$ 。令 $x_i$ 是在 $P_i$ 上的x的邻点。令 $T_i=P_i\cup x_i^{v_2}{P}_i^{v_2}z\cup x_i^{v_2}{x}_i$ ， $1\le i\le a+1$ ； ${T^{\prime }}_j=P_1^{v_j}\cup x{x}^{v_j}\cup y{y}^{v_j}\cup z{y}^{v_j}$ ， $3\le j\le n_k$ 。显然， $T_1,T_2,\cdots ,T_{a+1},{T^{\prime }}_3,\cdots ,{T^{\prime }}_{n_k}$ 是b棵内部不交的S-斯坦纳树。

情形3：S中的三个顶点分别属于不同的 $G^{v_i}$ ， $1\le i\le n_k$ 。

不失一般性，假设 $x\in G^{v_1}$ ， $y\in G^{v_2}$ ， $z\in G^{v_3}$ 。下面分三种子情形讨论。

子情形3.1： $S\subseteq K_{n_k}^{u_i}$ ， $1\le i\le n$ 。

不失一般性，假设 $S\subseteq K_{n_k}^{u_1}$ 。因为 $\kappa \left(G\right)=\delta \left(G\right)=a+1$ ，所以在 $G^{v_1}$ 中，顶点x有 $a+1$ 个邻点，记作 $x_1,x_2,\cdots ,x_{a+1}$ 。令 $T_i=x{x}_i\cup y{x}_i^{v_2}\cup z{x}_i^{v_3}\cup x_i{x}_i^{v_2}\cup x_i^{v_2}{x}_i^{v_3}$ ， $1\le i\le a+1$ 。又因为 $K_{n_k}$ 是完全图，所以由定理2.1知， ${\kappa }_3\left(K_{n_k}\right)=n_k-2$ ，故在 $K_{n_k}^{u_1}$ 中有 $n_k-2$ 棵内部不交的S-斯坦纳树，记作 ${T^{\prime }}_1,\cdots ,{T^{\prime }}_{n_k-2}$ 。显然， $T_1,T_2,\cdots ,T_{a+1},{T^{\prime }}_1,\cdots ,{T^{\prime }}_{n_k-2}$ 是b棵内部不交的S-斯坦纳树。

子情形3.2： $x,y\in K_{n_k}^{u_s}$ ， $z\in K_{n_k}^{u_t}$ ， $s\ne t$ 。

因为 $\kappa \left(G\right)=\delta \left(G\right)=a+1$ ， $G^{v_1}\cong G$ ，所以由定理2.3知，在 $G^{v_1}$ 中存在 $a+1$ 条内部不交的 $x{z}^{v_1}$ -路 $P_i$ ， $1\le i\le a+1$ 。因为图G是简单图，所以在 $G^{v_1}$ 中可以找到a条长度至少为2的 $x{z}^{v_1}$ -路 $P_i$ ， $1\le i\le a$ 。令 $x_i$ 是在 $P_i$ 上的x的邻点。令 $T_i=x{P}_i{x}_i\cup x_i^{v_2}{P}_i^{v_2}y\cup x_i^{v_3}{P}_i^{v_3}z\cup x_i^{v_2}{x}_i\cup x_i^{v_2}{x}_i^{v_3}$ ， $1\le i\le a$ ； $T_{a+1}=P_{a+1}^{v_2}\cup xy\cup z{z}^{v_2}$ ； $T_{a+2}=x{x}^{v_3}\cup y{x}^{v_3}\cup P_{a+1}^{v_3}$ ； ${T^{\prime }}_j=P_1^{v_j}\cup x^{v_j}x\cup x^{v_j}y\cup z^{v_j}z$ ， $4\le j\le n_k$ 。显然， $T_1,T_2,\cdots ,T_{a+2},{T^{\prime }}_4,\cdots ,{T^{\prime }}_{n_k}$ 是b棵内部不交的S-斯坦纳树。

子情形3.3： $x\in K_{n_k}^{u_i}$ ， $y\in K_{n_k}^{u_l}$ ， $z\in K_{n_k}^{u_m}$ ，其中 $i,l,m$ 不相等。

令 $x=\left(u_i,v_1\right),y=\left(u_l,v_2\right),z=\left(u_m,v_3\right)$ ， $S^{\prime }=\left\{\left(u_c,v_j\right)|c=i,l,m;j=1,2,3\right\}$ 。考虑如下两种情况。

如果在G中， $u_i,u_l,u_m$ 中的某两个顶点不相邻。不失一般性，假设在G中 $u_i,u_l$ 不相邻。因为 $\kappa \left(G\right)=\delta \left(G\right)=a+1$ ，所以在G中存在 $a+1$ 条内部不交的 $u_i{u}_l$ -路，记作 $P_j$ ，设 $u_{i_j}$ 是 $u_i$ 的邻点， $1\le j\le a+1$ 。假设 $u_m$ 不在 $P_j$ 上， $1\le j\le a$ 。由引理2.4知，在G中存在一个从 $u_m$ 到 $\left\{u_{i_1},u_{i_2},\cdots ,u_{i_a},u_i\right\}$ 的 $\left(a+1\right)$ -扇，记作 $Q_j$ ，其中有一条 $u_{i_j}{u}_m$ -路， $1\le j\le a$ ， $Q_{a+1}$ 是一条 $u_m{u}_i$ -路。令 $H_j={\left(u_i{u}_{i_j}\right)}^{v_1}\cup K_{n_k}^{u_{i_j}}\cup {\left(P_j-u_i\right)}^{v_2}\cup Q_j^{v_3}$ ， $1\le j\le a$ 。因为每个 $H_j$ 有一棵支撑树 $T_j$ ， $1\le j\le a$ ，所以我们找到a棵内部不交的S-斯坦纳树，记作 $$ 。因为 $K_{n_k}$ 是 $\left(n_k-1\right)$ -连通的，所以在 $K_{n_k}$ 中存在 $n_k-1$ 条内部不交的 $v_1{v}_2$ -路，记作 $R_j$ ，设 $v_{i_j}$ 是 $v_2$ 的邻点， $1\le j\le n_k-1$ 。又因为 $K_{n_k}$ 是完全图，所以可假设 $v_{i_1},v_{i_2},\cdots ,v_{i_{n_k-3}}\ne v_1,v_3$ ，令 $v_{i_{n_k-2}}=v_3$ ， $v_{i_{n_k-1}}=v_1$ ，故 $R_{n_k-2}-v_2=v_1{v}_3$ ， $R_{n_k-1}=v_1{v}_2$ 。

因为 $\kappa \left(K_{n_k}\right)=n_k-1$ ，所以在 $K_{n_k}-v_1$ 中存在一个从 $v_3$ 到 $\left\{v_{i_1},v_{i_2},\cdots ,v_{i_{n_{k-3}}},v_2\right\}$ 的 $\left(n_k-2\right)$ -扇，记作 $S_j$ ，其中有一条 $v_{i_j}{v}_3$ -路， $1\le j\le n_k-3$ ，有一条 $v_2{v}_3$ -路 $S_{n_k-2}$ 。令 ${T^{\prime }}_j={\left(R_j-v_2\right)}^{u_i}\cup {\left(G-\left\{u_{i_1},u_{i_2},\cdots ,u_{i_a}\right\}\right)}^{v_{i_j}}\cup {\left(v_{i_j}{v}_2\right)}^{u_l}\cup S_j^{u_m}$ ， $1\le j\le n_k-3$ ； ${T^{\prime }}_{n_k-2}={\left(v_1{v}_2\right)}^{u_i}\cup {\left(G-\left\{u_{i_1},u_{i_2},\cdots ,u_{i_a}\right\}\right)}^{v_2}\cup S_{n_k-2}^{u_m}$ ； ${T^{\prime }}_{n_k-1}={\left(v_1{v}_3\right)}^{u_i}\cup Q_{a+1}^{v_3}\cup P_{a+1}^{v_1}\cup {\left(v_1{v}_2\right)}^{u_l}$ 。显然， $T_1,T_2,\cdots ,T_a,{T^{\prime }}_1,\cdots ,{T^{\prime }}_{n_k-1}$ 是b棵内部不交的S-斯坦纳树(如图1所示)。

Figure 1. Solid lines in bold for $T_j$ , $1\le j\le a$ ; Solid lines for ${T^{\prime }}_j$ , $1\le j\le n_k-3$ ; Dashed lines for ${T^{\prime }}_{n_k-2}$ ; Dashed lines in bold for ${T^{\prime }}_{n_k-1}$

图1. 粗实线表示 $T_j$ ， $1\le j\le a$ ；细实线表示 ${T^{\prime }}_j$ , $1\le j\le n_k-3$ ；细虚线表示 ${T^{\prime }}_{n_k-2}$ ；粗虚线表示 ${T^{\prime }}_{n_k-1}$

如果在G中， $u_i,u_l,u_m$ 两两相邻。由引理2.7知，在 $\left(G\square K_{n_k}\right)\left(S^{\prime }\right)$ 中有3条内部不交的S-斯坦纳树，记作 ${T^{″}}_1,{T^{″}}_2,{T^{″}}_3$ 。因为G是 $\left(a+1\right)$ -连通的，所以 $\kappa \left(\left(G-u_m\right)-u_i{u}_l\right)\ge a-1$ ，故在 $\left(G-u_m\right)-u_i{u}_l$ 中存在 $a-1$ 条内部不交的 $u_i{u}_l$ -路，记作 $P_j$ 。令 $u_{i_j}$ 是 $u_i$ 的邻点， $1\le j\le a-1$ 。由引理2.4知，在 $G-u_i-u_l$ 中存在一个从 $u_m$ 到 $\left\{u_{i_1},u_{i_2},\cdots ,u_{i_{a-1}}\right\}$ 的 $\left(a-1\right)$ -扇。类似于情况1，可以构造 $a-1$ 棵内部不交的S-斯坦纳树 $T_1,T_2,\cdots ,T_{a-1}$ 。又因为 $\kappa \left(K_{n_k}\right)=n_k-1$ ，所以可以构造 $n_k-3$ 棵内部不交的S-斯坦纳树 ${T^{\prime }}_1,{T^{\prime }}_2,\cdots ,{T^{\prime }}_{n_k-3}$ 。显然， $T_1,T_2,\cdots ,T_{a-1},{T^{\prime }}_1,{T^{\prime }}_2,\cdots ,{T^{\prime }}_{n_k-3},{T^{″}}_1,{T^{″}}_2,{T^{″}}_3$ 是b棵内部不交的S-斯坦纳树。

基金项目

国家自然科学基金（No. 11401181）。

致谢

作者非常感谢审稿人和编辑的宝贵意见和建议，改善了本文的呈现。