完全图的笛卡尔积的广义3-连通度 The Generalized 3-Connectivity of Cartesian Product of Complete Graphs

doi:10.12677/AAM.2019.82036

Advances in Applied Mathematics
Vol. 08 No. 02 ( 2019 ), Article ID: 29025 , 7 pages
10.12677/AAM.2019.82036

The Generalized 3-Connectivity of Cartesian Product of Complete Graphs

Hengzhe Li, Yuanyuan Lu, Jiajia Wang

●How to Cite this Article

College of Mathematics and Information Science, Henan Normal University, Xinxiang Henan

Received: Feb. 3^rd, 2019; accepted: Feb. 18^th, 2019; published: Feb. 26^th, 2019

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 \subseteq V (T)$ . Two S-Steiner trees $T_{1}$ and $T_{2}$ are internally disjoint if $E (T_{1}) \cap E (T_{2}) = \emptyset$ and $V (T_{1}) \cap V (T_{2}) = S$ . Let $κ_{G} (S)$ be the maximum number of internally disjoint S-Steiner trees in G, and let $κ_{k} (G)$ be the minimum $κ_{G} (S)$ for S ranges over all k-subsets of $V (G)$ . In this paper, we study the $κ_{3}$ -connectivity of Cartesian product of complete graphs, determine $κ_{3} (K_{n_{1}} □ K_{n_{2}}) = n_{1} + n_{2} - 3$ for any two complete graphs; $κ_{3} (K_{n_{1}} □ K_{n_{2}} □ \dots □ K_{n_{k}}) = \sum_{i = 1}^{k} n_{i} - k - 1$ for any k complete graphs, where $k \geq 2$ .

Keywords:Complete Graphs, $κ_{3}$ -Connectivity, Cartesian Product

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

李恒哲，芦园园，王佳佳

河南师范大学数学和信息科学学院，河南新乡

收稿日期：2019年2月3日；录用日期：2019年2月18日；发布日期：2019年2月26日

摘要

设S是图G中至少有2个顶点的集合，T是G的一棵子树。如果 $S \subseteq V (T)$ ，则称T是G的一棵S-斯坦纳树。设 $T_{1}$ 与 $T_{2}$ 是S-斯坦纳树，如果 $E (T_{1}) \cap E (T_{2}) = \emptyset$ 且 $V (T_{1}) \cap V (T_{2}) = S$ ，则称 $T_{1}$ 与 $T_{2}$ 是内部不交的S-斯坦纳树。 $κ_{G} (S)$ 表示图G中内部不交的S-斯坦纳树的最大数目， $κ_{k} (G)$ 是当S遍及 $V (G)$ 的所有k元子集时的最小的 $κ_{G} (S)$ 。在本文中，我们研究完全图的笛卡尔积的 $κ_{3}$ -连通度。对于任意两个完全图 $K_{n_{1}}$ 与 $K_{n_{2}}$ ，确定 $κ_{3} (K_{n_{1}} □ K_{n_{2}}) = n_{1} + n_{2} - 3$ ；对于任意 $k (k \geq 2)$ 个完全图，确定 $κ_{3} (K_{n_{1}} □ K_{n_{2}} □ \dots □ K_{n_{k}}) = \sum_{i = 1}^{k} n_{i} - k - 1$ 。

关键词 :完全图， $κ_{3}$ -连通度，笛卡尔积

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

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

设图G是一个连通图，S是图G中至少有2个顶点的集合，T是G的一棵子树。如果 $S \subseteq V (T)$ ，则称T是G的一棵S-斯坦纳树。设 $T_{1}$ 与 $T_{2}$ 是S-斯坦纳树，如果 $E (T_{1}) \cap E (T_{2}) = \emptyset$ 且 $V (T_{1}) \cap V (T_{2}) = S$ ，则称 $T_{1}$ 与 $T_{2}$ 是内部不交的S-斯坦纳树。对于 $V (G)$ 的一个子集S， $κ_{G} (S)$ 表示图G中内部不交的S-斯坦纳树的最大数目。如果 $S = {x, y}$ ，则 $κ_{G} (S) = κ_{G} ({x, y})$ 是局部点连通度。对于 $k \geq 2$ 的整数， $κ_{k} (G)$ 是当S遍及 $V (G)$ 的所有k元子集时的最小的 $κ_{G} (S)$ ，称它为广义k-连通度，简称 $κ_{k}$ -连通度。Chartrand等人 [2] 引入了 $κ_{k}$ -连通度。显然，当 $| S | = 2$ 时， $κ_{2} (G) = κ (G)$ 。

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

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

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

2. 预备知识

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

设G与H是两个图，顶点集分别为 $V (G) = {u_{1}, u_{2}, \dots, u_{n}}$ ， $V (H) = {v_{1}, v_{2}, \dots, v_{m}}$ 。我们用 $G (u_{i}, v_{j})$ 来表示 $G □ H$ 的子图，这个子图是由顶点集 ${(u_{i}, v_{j}) | 1 \leq i \leq n}$ 诱导出来的。类似的，我们用 $H (u_{i}, v_{j})$ 来表示 $G □ H$ 的子图，这个子图是由顶点集 ${(u_{i}, v_{j}) | 1 \leq j \leq m}$ 诱导出来的。显然，对于图G中的不同顶点 $u_{i_{1}}$ 与 $u_{i_{2}}$ ，有 $G (u_{i_{1}}, v_{j}) = G (u_{i_{2}}, v_{j})$ 。为了简单，我们可以用 $G^{v_{j}}$ 来代替 $G (u_{i}, v_{j}) (1 \leq i \leq n)$ 。类似的，我们也可以用 $H^{u_{i}}$ 来代替 $H (u_{i}, v_{j}) (1 \leq j \leq m)$ 。下面的几个符号可以简化我们的证明。

给定一个顶点 $v_{a} \in V (H)$ ，对于 $V (G)$ 中的任意顶点u，有 $u^{v_{a}} : = (u, v_{a})$ ，对于G中的任意子图 $G_{1}$ ，有 $G_{1}^{v_{a}} : = (V (G_{1}^{v_{a}}), E (G_{1}^{v_{a}}))$ ，其中 $V (G_{1}^{v_{a}}) = {(u, v_{a}) : u \in V (G_{1})}$ ， $E (G_{1}^{v_{a}}) = {(u, v_{a}) (u^{'}, v_{a}) : u u^{'} \in E (G_{1})}$ 。

给定一个顶点 $v_{b} \in V (H)$ ，对于任意顶点 $(u, v_{a}) \in V (G^{v_{a}})$ ，有 ${(u, v_{a})}^{v_{b}} : = (u, v_{b})$ ，对于任意子图，有 $G_{1}^{v_{b}} : = (V (G_{1}^{v_{b}}), E (G_{1}^{v_{b}}))$ ，其中 $V (G_{1}^{v_{b}}) = {(u, v_{b}) : (u, v_{a}) \in V (G_{1}^{v_{a}})}$ ， $E (G_{1}^{v_{b}}) = {(u, v_{b}) (u^{'}, v_{b}) : (u, v_{a}) (u^{'}, v_{a}) \in E (G_{1}^{v_{a}})}$ 。

类似的，给定一个顶点 $u_{a} \in V (G)$ ，对于 $v \in V (H)$ 可以定义映射 $v^{u_{a}}$ ，对于 $H_{1} \subseteq H$ 可以定义映射 $H_{1}^{u_{a}}$ ；给定一个顶点 $u_{b} \in V (G)$ ，对于 $(u_{a}, v) \in V (H^{u_{a}})$ 可以定义映射 ${(u_{a}, v)}^{u_{b}}$ ，对于 $H_{1} \subseteq H^{u_{a}}$ 可以定义映射 $H_{1}^{u_{b}}$ 。

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

定理2.1 [10] ：对于任意两个整数n和k， $2 \leq k \leq n$ ，有 $κ_{k} (K_{n}) = n - ⌈ \frac{k}{2} ⌉$ 。

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

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

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

定理2.5 [20] ： $κ_{4} (Q_{k}) = k - 1$ ， $k \geq 2$ 。

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

引理2.7 [17] ：设 $C_{1}, C_{2}, \dots, C_{k}$ 是k个圈，则 $κ_{3} (C_{1} □ C_{2} □ \dots □ C_{k}) = 2 k - 1$ 。

3. 主要定理及其证明

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

定理3.1：对于任意两个完全图 $K_{n_{1}}$ 与 $K_{n_{2}}$ ，有 $κ_{3} (K_{n_{1}} □ K_{n_{2}}) = n_{1} + n_{2} - 3$ 。

证明：根据 $n_{1}$ 与 $n_{2}$ 的取值情况，考虑如下三种情形。

情形1： $n_{1} = n_{2} = 2$ 。

因为 $n_{1} = n_{2} = 2$ ，所以两个完全图都是 $K_{2}$ 。显然， $κ_{3} (K_{2} □ K_{2}) = κ_{3} (C_{4}) = 1 = 2 + 2 - 3$ 。

情形2： $n_{1} \geq 3, n_{2} = 2$ 。

由引理2.2知， $κ_{3} (K_{n_{1}} □ K_{2}) \leq δ (K_{n_{1}} □ K_{2}) - 1 = n_{1} - 1$ ，故只需证 $κ_{3} (K_{n_{1}} □ K_{2}) \geq n_{1} - 1$ 。令 $V (K_{n_{1}}) = {u_{1}, u_{2}, \dots, u_{n_{1}}}$ ， $V (K_{2}) = {v_{1}, v_{2}}$ ， $S = {x, y, z} \subseteq V (K_{n_{1}} □ K_{2})$ 。下面分两种子情形讨论。

子情形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}, \dots, 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}, \dots, 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}}$ 。因为 $κ (K_{n_{1}}) = n_{1} - 1$ ， $K_{n_{1}}^{v_{i}} ≅ K_{n_{1}}$ ， $i = 1, 2$ ，所以由定理2.3知，在 $K_{n_{1}}^{v_{1}}$ 中存在 $n_{1} - 1$ 条内部不交的xy-路， $1 \leq i \leq n_{1} - 1$ ，在 $K_{n_{1}}^{v_{2}}$ 中存在 $n_{1} - 1$ 条内部不交的 $x^{v_{2}} z$ -路 $Q_{i}$ ， $1 \leq i \leq 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 \leq i \leq n_{1} - 1$ 。显然， $T_{1}, T_{2}, \dots, T_{n_{1} - 1}$ 是 $n_{1} - 1$ 棵内部不交的S-斯坦纳树。

情形3： $n_{1} \geq 3, n_{2} \geq 3$ 。

由引理2.2知， $κ_{3} (K_{n_{1}} □ K_{n_{2}}) \leq δ (K_{n_{1}} □ K_{n_{2}}) - 1 = n_{1} + n_{2} - 3$ ，故只需证 $κ_{3} (K_{n_{1}} □ K_{n_{2}}) \geq n_{1} + n_{2} - 3$ 。令 $V (K_{n_{1}}) = {u_{1}, u_{2}, \dots, u_{n_{1}}}$ ， $V (K_{n_{2}}) = {v_{1}, v_{2}, \dots, v_{n_{2}}}$ ， $S = {x, y, z} \subseteq V (K_{n_{1}} □ K_{n_{2}})$ 。下面分三种子情形讨论。

子情形3.1： $S \subseteq K_{n_{1}}^{v_{i}}$ ， $1 \leq i \leq n_{2}$ 。

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

子情形3.2：S中的某两个顶点属于某个 $K_{n_{1}}^{v_{i}}$ ， $1 \leq i \leq n_{2}$ 。

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

子情形3.3：S中的三个顶点分别属于不同的 $K_{n_{1}}^{v_{i}}$ ， $1 \leq i \leq 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知， $κ_{3} (K_{n_{2}}^{u_{1}}) = n_{2} - 2$ ，所以在 $K_{n_{2}}^{u_{1}}$ 中有 $n_{2} - 2$ 棵内部不交的S-斯坦纳树，记作 $T_{1}, T_{2}, \dots, T_{n_{2} - 2}$ 。令 ${T^{'}}_{i} = T_{1}^{u_{i}} \cup x x^{u_{i}} \cup y y^{u_{i}} \cup z z^{u_{i}}$ ， $2 \leq i \leq n_{1}$ 。显然， $T_{1}, T_{2}, \dots, T_{n_{2} - 2}, {T^{'}}_{2}, \dots, {T^{'}}_{n_{1}}$ 是 $n_{1} + n_{2} - 3$ 棵内部不交的S-斯坦纳树。

如果 $x, y \in K_{n_{2}}^{u_{s}}$ ， $z \in K_{n_{2}}^{u_{t}}$ , 其中 $s \neq t$ 。因为 $κ (K_{n_{1}}) = n_{1} - 1$ ， $K_{n_{1}}^{v_{1}} ≅ K_{n_{1}}$ ，所以由定理2.3知，在 $K_{n_{1}}^{v_{1}}$ 中存在 $n_{1} - 1$ 条内部不交的 $x z^{v_{1}}$ -路 $P_{i}$ ， $1 \leq i \leq n_{1} - 1$ 。因为 $K_{n_{1}}$ 是简单图，所以在 $K_{n_{1}}^{v_{1}}$ 中可以找到 $n_{1} - 2$ 条长度至少为2的 $x z^{v_{1}}$ -路 $P_{i}$ ， $1 \leq i \leq 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 \leq i \leq 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}} = x y \cup y y^{v_{3}} \cup P_{n_{1} - 1}^{v_{3}}$ ； ${T^{'}}_{j} = x^{v_{j}} x \cup x^{v_{j}} y \cup z^{v_{j}} z \cup P_{1}^{v_{j}}$ ， $4 \leq j \leq n_{2}$ 。显然， $T_{1}, T_{2}, \dots, T_{n_{1}}, {T^{'}}_{4}, \dots, {T^{'}}_{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知， $κ_{3} (K_{3} □ K_{3}) = κ_{3} (C_{3} □ C_{3}) = 3$ ，故定理成立。当 $n_{1} \geq 4$ 和 $n_{2} \geq 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 \leq i \leq n_{1} - 3$ 。令 ${T^{'}}_{1} = x y^{v_{1}} \cup y^{v_{1}} z^{v_{1}} \cup y y^{v_{1}} \cup z z^{v_{1}}$ ； ${T^{'}}_{2} = x x^{v_{2}} \cup x^{v_{2}} y \cup y z^{v_{2}} \cup z^{v_{2}} z$ ； ${T^{'}}_{3} = x x^{v_{3}} \cup x^{v_{3}} y^{v_{3}} \cup y^{v_{3}} z \cup y^{v_{3}} y$ ； ${T^{'}}_{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 \leq j \leq n_{2}$ 。显然， $T_{1}, T_{2}, \dots, T_{n_{1} - 3}, {T^{'}}_{1}, \dots, {T^{'}}_{n_{2}}$ 是 $n_{1} + n_{2} - 3$ 棵内部不交的S-斯坦纳树。

定理3.2：对于任意 $k (k \geq 2)$ 个完全图，有 $κ_{3} (K_{n_{1}} □ K_{n_{2}} □ \dots □ K_{n_{k}}) = \sum_{i = 1}^{k} n_{i} - k - 1$ 。

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

接下来只讨论 $n_{k} \geq 3$ 即可。当 $k = 2$ 时，由定理3.1知，定理成立；假设对于任意不超过 $k - 1$ 个完全图的笛卡尔积，定理都成立，即 $κ_{3} (K_{n_{1}} □ K_{n_{2}} □ \dots □ K_{n_{k - 1}}) = \sum_{i = 1}^{k - 1} n_{i} - k$ 成立；现在证明对于任意k个完全图的笛卡尔积，定理成立。由引理2.2知， $κ_{3} (K_{n_{1}} □ K_{n_{2}} □ \dots □ K_{n_{k}}) \leq δ (K_{n_{1}} □ K_{n_{2}} □ \dots □ K_{n_{k}}) - 1 = \sum_{i = 1}^{k} n_{i} - k - 1$ ，故只需证 $κ_{3} (K_{n_{1}} □ K_{n_{2}} □ \dots □ K_{n_{k}}) \geq \sum_{i = 1}^{k} n_{i} - k - 1$ 。为了简便，令图G表示图 $K_{n_{1}} □ K_{n_{2}} □ \dots □ K_{n_{k - 1}}$ ， $a = \sum_{i = 1}^{k - 1} n_{i} - k$ ， $b = \sum_{i = 1}^{k} n_{i} - k - 1$ 。令 $V (G) = {u_{1}, u_{2}, \dots, u_{n}}$ ， $V (K_{n_{k}}) = {v_{1}, v_{2}, \dots, v_{n_{k}}}$ ， $S = {x, y, z} \subseteq V (G □ K_{n_{k}})$ 。考虑如下三种情形。

情形1： $S \subseteq G^{v_{i}}$ ， $1 \leq i \leq n_{k}$ 。

不失一般性，假设 $S \subseteq G^{v_{1}}$ 。由归纳假设知，在 $G^{v_{1}}$ 中可以找到a棵内部不交的S-斯坦纳树，记作 $T_{1}, T_{2}, \dots, T_{a}$ 。我们只需在 $G^{v_{1}}$ 外找 $n_{k} - 1$ 棵内部不交的S-斯坦纳树，令 ${T^{'}}_{i} = T_{1}^{v_{i}} \cup x x^{v_{i}} \cup y y^{v_{i}} \cup z z^{v_{i}}$ ， $2 \leq i \leq n_{k}$ 。显然， $T_{1}, T_{2}, \dots, T_{a}, {T^{'}}_{2}, \dots, {T^{'}}_{n_{k}}$ 是b棵内部不交的S-斯坦纳树。

情形2：S中的某两个顶点属于某个 $G^{v_{i}}$ ， $1 \leq i \leq n_{k}$ 。

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

子情形2.1： $| z^{v_{1}} \cap {x, y} | = 0$ 。

因为 $κ (G) = δ (G) = a + 1$ ， $G^{v_{i}} ≅ G$ ， $i = 1, 2, \dots, n_{k}$ ，所以由定理2.3知，在 $G^{v_{1}}$ 中存在 $a + 1$ 条内部不交的xy-路 $P_{i}$ ， $1 \leq i \leq a + 1$ ，在 $G^{v_{2}}$ 中存在 $a + 1$ 条内部不交的 $x^{v_{2}} z$ -路 $Q_{i}$ ， $1 \leq i \leq a + 1$ 。令 $x_{i}$ 是在 $P_{i}$ 上的x的邻点。在 $G^{v_{j}}$ 中任取一棵 ${x^{v_{j}}, y^{v_{j}}, z^{v_{j}}}$ -斯坦纳树 $R^{v_{j}}$ ， $3 \leq j \leq n_{k}$ 。令 $T_{i} = P_{i} \cup x_{i}^{v_{2}} Q_{i} z \cup x_{i}^{v_{2}} x_{i}$ ， $1 \leq i \leq a + 1$ ； ${T^{'}}_{j} = R^{v_{j}} \cup x x^{v_{j}} \cup y y^{v_{j}} \cup z z^{v_{j}}$ ， $3 \leq j \leq n_{k}$ 。显然， $T_{1}, T_{2}, \dots, T_{a + 1}, {T^{'}}_{3}, \dots, {T^{'}}_{n_{k}}$ 是b棵内部不交的S-斯坦纳树。

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

不失一般性，假设 $z^{v_{1}} = y$ 。因为 $κ (G) = δ (G) = a + 1$ ， $G^{v_{1}} ≅ G$ ，所以由定理2.3知，在中存在 $a + 1$ 条内部不交的xy-路 $P_{i}$ ， $1 \leq i \leq 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 \leq i \leq a + 1$ ； ${T^{'}}_{j} = P_{1}^{v_{j}} \cup x x^{v_{j}} \cup y y^{v_{j}} \cup z y^{v_{j}}$ ， $3 \leq j \leq n_{k}$ 。显然， $T_{1}, T_{2}, \dots, T_{a + 1}, {T^{'}}_{3}, \dots, {T^{'}}_{n_{k}}$ 是b棵内部不交的S-斯坦纳树。

情形3：S中的三个顶点分别属于不同的 $G^{v_{i}}$ ， $1 \leq i \leq 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 \leq i \leq n$ 。

不失一般性，假设 $S \subseteq K_{n_{k}}^{u_{1}}$ 。因为 $κ (G) = δ (G) = a + 1$ ，所以在 $G^{v_{1}}$ 中，顶点x有 $a + 1$ 个邻点，记作 $x_{1}, x_{2}, \dots, 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 \leq i \leq a + 1$ 。又因为 $K_{n_{k}}$ 是完全图，所以由定理2.1知， $κ_{3} (K_{n_{k}}) = n_{k} - 2$ ，故在 $K_{n_{k}}^{u_{1}}$ 中有 $n_{k} - 2$ 棵内部不交的S-斯坦纳树，记作 ${T^{'}}_{1}, \dots, {T^{'}}_{n_{k} - 2}$ 。显然， $T_{1}, T_{2}, \dots, T_{a + 1}, {T^{'}}_{1}, \dots, {T^{'}}_{n_{k} - 2}$ 是b棵内部不交的S-斯坦纳树。

子情形3.2： $x, y \in K_{n_{k}}^{u_{s}}$ ， $z \in K_{n_{k}}^{u_{t}}$ ， $s \neq t$ 。

因为 $κ (G) = δ (G) = a + 1$ ， $G^{v_{1}} ≅ G$ ，所以由定理2.3知，在 $G^{v_{1}}$ 中存在 $a + 1$ 条内部不交的 $x z^{v_{1}}$ -路 $P_{i}$ ， $1 \leq i \leq a + 1$ 。因为图G是简单图，所以在 $G^{v_{1}}$ 中可以找到a条长度至少为2的 $x z^{v_{1}}$ -路 $P_{i}$ ， $1 \leq i \leq 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 \leq i \leq a$ ； $T_{a + 1} = P_{a + 1}^{v_{2}} \cup x y \cup z z^{v_{2}}$ ； $T_{a + 2} = x x^{v_{3}} \cup y x^{v_{3}} \cup P_{a + 1}^{v_{3}}$ ； ${T^{'}}_{j} = P_{1}^{v_{j}} \cup x^{v_{j}} x \cup x^{v_{j}} y \cup z^{v_{j}} z$ ， $4 \leq j \leq n_{k}$ 。显然， $T_{1}, T_{2}, \dots, T_{a + 2}, {T^{'}}_{4}, \dots, {T^{'}}_{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 = (u_{i}, v_{1}), y = (u_{l}, v_{2}), z = (u_{m}, v_{3})$ ， $S^{'} = {(u_{c}, v_{j}) | c = i, l, m; j = 1, 2, 3}$ 。考虑如下两种情况。

如果在G中， $u_{i}, u_{l}, u_{m}$ 中的某两个顶点不相邻。不失一般性，假设在G中 $u_{i}, u_{l}$ 不相邻。因为 $κ (G) = δ (G) = a + 1$ ，所以在G中存在 $a + 1$ 条内部不交的 $u_{i} u_{l}$ -路，记作 $P_{j}$ ，设 $u_{i_{j}}$ 是 $u_{i}$ 的邻点， $1 \leq j \leq a + 1$ 。假设 $u_{m}$ 不在 $P_{j}$ 上， $1 \leq j \leq a$ 。由引理2.4知，在G中存在一个从 $u_{m}$ 到 ${u_{i_{1}}, u_{i_{2}}, \dots, u_{i_{a}}, u_{i}}$ 的 $(a + 1)$ -扇，记作 $Q_{j}$ ，其中有一条 $u_{i_{j}} u_{m}$ -路， $1 \leq j \leq a$ ， $Q_{a + 1}$ 是一条 $u_{m} u_{i}$ -路。令 $H_{j} = {(u_{i} u_{i_{j}})}^{v_{1}} \cup K_{n_{k}}^{u_{i_{j}}} \cup {(P_{j} - u_{i})}^{v_{2}} \cup Q_{j}^{v_{3}}$ ， $1 \leq j \leq a$ 。因为每个 $H_{j}$ 有一棵支撑树 $T_{j}$ ， $1 \leq j \leq a$ ，所以我们找到a棵内部不交的S-斯坦纳树，记作。因为 $K_{n_{k}}$ 是 $(n_{k} - 1)$ -连通的，所以在 $K_{n_{k}}$ 中存在 $n_{k} - 1$ 条内部不交的 $v_{1} v_{2}$ -路，记作 $R_{j}$ ，设 $v_{i_{j}}$ 是 $v_{2}$ 的邻点， $1 \leq j \leq n_{k} - 1$ 。又因为 $K_{n_{k}}$ 是完全图，所以可假设 $v_{i_{1}}, v_{i_{2}}, \dots, v_{i_{n_{k} - 3}} \neq 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}$ 。

因为 $κ (K_{n_{k}}) = n_{k} - 1$ ，所以在 $K_{n_{k}} - v_{1}$ 中存在一个从 $v_{3}$ 到 ${v_{i_{1}}, v_{i_{2}}, \dots, v_{i_{n_{k - 3}}}, v_{2}}$ 的 $(n_{k} - 2)$ -扇，记作 $S_{j}$ ，其中有一条 $v_{i_{j}} v_{3}$ -路， $1 \leq j \leq n_{k} - 3$ ，有一条 $v_{2} v_{3}$ -路 $S_{n_{k} - 2}$ 。令 ${T^{'}}_{j} = {(R_{j} - v_{2})}^{u_{i}} \cup {(G - {u_{i_{1}}, u_{i_{2}}, \dots, u_{i_{a}}})}^{v_{i_{j}}} \cup {(v_{i_{j}} v_{2})}^{u_{l}} \cup S_{j}^{u_{m}}$ ， $1 \leq j \leq n_{k} - 3$ ； ${T^{'}}_{n_{k} - 2} = {(v_{1} v_{2})}^{u_{i}} \cup {(G - {u_{i_{1}}, u_{i_{2}}, \dots, u_{i_{a}}})}^{v_{2}} \cup S_{n_{k} - 2}^{u_{m}}$ ； ${T^{'}}_{n_{k} - 1} = {(v_{1} v_{3})}^{u_{i}} \cup Q_{a + 1}^{v_{3}} \cup P_{a + 1}^{v_{1}} \cup {(v_{1} v_{2})}^{u_{l}}$ 。显然， $T_{1}, T_{2}, \dots, T_{a}, {T^{'}}_{1}, \dots, {T^{'}}_{n_{k} - 1}$ 是b棵内部不交的S-斯坦纳树(如图1所示)。

Figure 1. Solid lines in bold for $T_{j}$ , $1 \leq j \leq a$ ; Solid lines for ${T^{'}}_{j}$ , $1 \leq j \leq n_{k} - 3$ ; Dashed lines for ${T^{'}}_{n_{k} - 2}$ ; Dashed lines in bold for ${T^{'}}_{n_{k} - 1}$

图1. 粗实线表示 $T_{j}$ ， $1 \leq j \leq a$ ；细实线表示 ${T^{'}}_{j}$ , $1 \leq j \leq n_{k} - 3$ ；细虚线表示 ${T^{'}}_{n_{k} - 2}$ ；粗虚线表示 ${T^{'}}_{n_{k} - 1}$

如果在G中， $u_{i}, u_{l}, u_{m}$ 两两相邻。由引理2.7知，在 $(G □ K_{n_{k}}) (S^{'})$ 中有3条内部不交的S-斯坦纳树，记作 ${T^{″}}_{1}, {T^{″}}_{2}, {T^{″}}_{3}$ 。因为G是 $(a + 1)$ -连通的，所以 $κ ((G - u_{m}) - u_{i} u_{l}) \geq a - 1$ ，故在 $(G - u_{m}) - u_{i} u_{l}$ 中存在 $a - 1$ 条内部不交的 $u_{i} u_{l}$ -路，记作 $P_{j}$ 。令 $u_{i_{j}}$ 是 $u_{i}$ 的邻点， $1 \leq j \leq a - 1$ 。由引理2.4知，在 $G - u_{i} - u_{l}$ 中存在一个从 $u_{m}$ 到 ${u_{i_{1}}, u_{i_{2}}, \dots, u_{i_{a - 1}}}$ 的 $(a - 1)$ -扇。类似于情况1，可以构造 $a - 1$ 棵内部不交的S-斯坦纳树 $T_{1}, T_{2}, \dots, T_{a - 1}$ 。又因为 $κ (K_{n_{k}}) = n_{k} - 1$ ，所以可以构造 $n_{k} - 3$ 棵内部不交的S-斯坦纳树 ${T^{'}}_{1}, {T^{'}}_{2}, \dots, {T^{'}}_{n_{k} - 3}$ 。显然， $T_{1}, T_{2}, \dots, T_{a - 1}, {T^{'}}_{1}, {T^{'}}_{2}, \dots, {T^{'}}_{n_{k} - 3}, {T^{″}}_{1}, {T^{″}}_{2}, {T^{″}}_{3}$ 是b棵内部不交的S-斯坦纳树。

基金项目

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

致谢

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

文章引用

李恒哲,芦园园,王佳佳. 完全图的笛卡尔积的广义3-连通度
The Generalized 3-Connectivity of Cartesian Product of Complete Graphs[J]. 应用数学进展, 2019, 08(02): 320-326. https://doi.org/10.12677/AAM.2019.82036

参考文献

1. Bondy, J.A. and Murty, U.S.R. (2008) Graph Theory, GTM 244. Springer, Berlin.

2. Chartrand, G., Kapoor, S.F., Lesniak, L. and Lick, D.R. (1984) Generalized Connectivity in Graphs. Bulletin of the Bombay Mathematical Colloquium, 2, 1-6.

3. Chiue, W.-S. and Shieh, B.-S. (1999) On Connectivity of Cartesian Product of Two Graphs. Applied Mathematics and Computation, 102, 129-137. https://doi.org/10.1016/S0096-3003(98)10041-3

4. Imrich, W. and Klavžar, S. (2000) Product Graphs. Structure and Recognition. Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley, New York.

5. Imrich, W., Klavžar, S. and Rall, D.F. (2008) Topics in Graph Theory. Graphs and Their Cartesian Product. AK Peters, Wellesley.

6. Klavžar, S. and Spacapan, S. (2008) On the Edge-Connectivity of Cartesian Product Graphs. Asian-European Journal of Mathematics, 1, 93-98.

7. Sabidussi, G. (1957) Graphs with Given Group and Given Graph-Theoretic Properties. Canadian Journal of Mathematics, 9, 515-525. https://doi.org/10.4153/CJM-1957-060-7

8. Špacapan, S. (2008) Connectivity of Cartesian Products of Graphs. Applied Mathematics Letters, 21, 682-685. https://doi.org/10.1016/j.aml.2007.06.010

9. Xu, J. and Yang, C. (2006) Connectivity of Cartesian Product Graphs. Discrete Mathematics, 306, 159-165. https://doi.org/10.1016/j.disc.2005.11.010

10. Chartrand, G., Okamoto, F. and Zhang, P. (2010) Rainbow Trees in Graphs and Generalized Connectivity. Networks, 55, 360-367.

11. Li, H. and Wang, J. (2018) The λ3-Connectivity and κ3-Connectivity of Recursive Circulants. Applied Mathematics and Computation, 339, 750-757. https://doi.org/10.1016/j.amc.2018.07.065

12. Li, H., Li, X. and Sun, Y. (2012) The Generalied 3-Connectivity of Cartesian Product Graphs. Discrete Mathematics and Theoretical Computer Science, 14, 43-54.

13. Li, S., Li, X. and Zhou, W. (2010) Sharp Bounds for the Generalized Connectivity κ3(G). Discrete Mathematics, 310, 2147-2163. https://doi.org/10.1016/j.disc.2010.04.011

14. Li, X. and Mao, Y. (2014) The Generalized 3-Connectivity of Lexicographic Product Graphs. Discrete Mathematics and Theoretical Computer Science, 16, 339-354.

15. Li, X., Mao, Y. and Sun, Y. (2014) On the Generalized (Edge-)Connectivity of Graphs. Australasian Journal of Combinatorics, 58, 304-319.

16. Li, H., Wu, B., Meng, J. and Ma, Y. (2018) Steiner Tree Packing Number and Tree Connectivity. Discrete Mathematics, 341, 1945-1951. https://doi.org/10.1016/j.disc.2018.03.021

17. Li, H., Ma, Y., Yang, W. and Wang, Y. (2017) The Generalized 3-Connectivity of Graph Products. Applied Mathematics and Computation, 295, 77-83. https://doi.org/10.1016/j.amc.2016.10.002

18. Li, X. and Mao, Y. (2016) Generalized Connectivity of Graphs. In: Springer Briefs in Math, Springer, New York. https://doi.org/10.1007/978-3-319-33828-6

19. Dirac, G.A. (1960) In abstrakten graphen vorhandene voll-standige 4-graphen und ihre unterteilungen. Mathematische Nachrichten, 22, 61-85. https://doi.org/10.1002/mana.19600220107

20. Lin, S. and Zhang, Q. (2017) The Generalized 4-Connectivity of Hypercubes. Discrete Applied Mathematics, 220, 60-67. https://doi.org/10.1016/j.dam.2016.12.003

期刊菜单