AAM  >> Vol. 8 No. 2 (February 2019)

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

  • 全文下载: PDF(749KB) HTML   XML   PP.320-326   DOI: 10.12677/AAM.2019.82036  
  • 下载量: 252  浏览量: 467   国家自然科学基金支持

作者:  

李恒哲,芦园园,王佳佳:河南师范大学数学和信息科学学院,河南 新乡

关键词:
完全图K3-连通度笛卡尔积Complete Graphs K3-Connectivity Cartesian Product

摘要:

设S是图G中至少有2个顶点的集合,T是G的一棵子树。如果S⊆V(T),则称T是G的一棵S-斯坦纳树。设T1与T2是S-斯坦纳树,如果E(T1)∩E(T2)=∅且V(T1)∩V(T2)=S,则称T1T2是内部不交的S-斯坦纳树。KG(S)表示图G中内部不交的S-斯坦纳树的最大数目,KK(G)是当S遍及V(G)的所有k元子集时的最小的KG(S)。在本文中,我们研究完全图的笛卡尔积的K3-连通度。对于任意两个完全图Kn1Kn2,确定K3(Kn1,Kn2)=n1+n2-3;对于任意K(K≥2)个完全图,确定K3(Kn1,Kn2,...,KnK)=∑i=1kni-K-1

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 T1 and T2 are internally disjoint if E(T1)∩E(T2)=∅ and V(T1)∩V(T2)=S. Let KG(S) be the maximum number of internally disjoint S-Steiner trees in G, and let KK(G) be the minimum KG(S) for S ranges over all k-subsets of V(G). In this paper, we study the K3-connectivity of Cartesian product of complete graphs, determine K3(Kn1,Kn2)=n1+n2-3 for any two complete graphs; K3(Kn1,Kn2,...,KnK)=∑i=1kni-K-1 for any k complete graphs, where K≥2.

1. 引言

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

设图G是一个连通图,S是图G中至少有2个顶点的集合,T是G的一棵子树。如果 S V ( T ) ,则称T是G的一棵S-斯坦纳树。设 T 1 T 2 是S-斯坦纳树,如果 E ( T 1 ) E ( T 2 ) = V ( T 1 ) 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 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 ) × V ( H ) ,两个顶点 ( u , v ) ( u , v ) 相邻当且仅当 u = u v v E ( H ) ,或 v = v u u E ( G ) 。特别地,n条路的笛卡尔积是n-维网格图。长为1的n条路的笛卡尔积是n-维超立方体。

设G与H是两个图,顶点集分别为 V ( G ) = { u 1 , u 2 , , u n } V ( H ) = { v 1 , v 2 , , v m } 。我们用 G ( u i , v j ) 来表示 G H 的子图,这个子图是由顶点集 { ( u i , v j ) | 1 i n } 诱导出来的。类似的,我们用 H ( u i , v j ) 来表示 G H 的子图,这个子图是由顶点集 { ( u i , v j ) | 1 j 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 i n ) 。类似的,我们也可以用 H u i 来代替 H ( u i , v j ) ( 1 j m ) 。下面的几个符号可以简化我们的证明。

给定一个顶点 v a 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 V ( G 1 ) } E ( G 1 v a ) = { ( u , v a ) ( u , v a ) : u u E ( G 1 ) }

给定一个顶点 v b V ( H ) ,对于任意顶点 ( u , v a ) 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 ) V ( G 1 v a ) } E ( G 1 v b ) = { ( u , v b ) ( u , v b ) : ( u , v a ) ( u , v a ) E ( G 1 v a ) }

类似的,给定一个顶点 u a V ( G ) ,对于 v V ( H ) 可以定义映射 v u a ,对于 H 1 H 可以定义映射 H 1 u a ;给定一个顶点 u b V ( G ) ,对于 ( u a , v ) V ( H u a ) 可以定义映射 ( u a , v ) u b ,对于 H 1 H u a 可以定义映射 H 1 u b

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

定理2.1 [10] :对于任意两个整数n和k, 2 k n ,有 κ k ( K n ) = n k 2

引理2.2 [13] :设图G是一个至少有3个顶点的连通图,如果图G有两个最小度为 δ ( G ) 的相邻顶点,则有 κ k ( G ) δ ( G ) 1 ;而且,上界是紧的。

定理2.3 [1] :设图G是一个k-连通图,如果x与y是G中的一对不同顶点,那么在图G中存在k条内部不交的xy-路 P 1 , P 2 , , P k

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

定理2.5 [20] : κ 4 ( Q k ) = k 1 k 2

引理2.6 [20] :设 k , r 是两个整数, k 4 ,G是一个r-正则图,如果 κ k ( G ) = r 1 ,那么 κ k 1 ( G ) = r 1

引理2.7 [17] :设 C 1 , C 2 , , C k 是k个圈,则 κ 3 ( C 1 C 2 C k ) = 2 k 1

3. 主要定理及其证明

在本文中, K n i 表示有 n i 个顶点的完全图,其中 1 i k 。一条xy-路是一条起始于x,终止于y的路。对于一条路P来说,其中 x , y 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 3 , n 2 = 2

由引理2.2知, κ 3 ( K n 1 K 2 ) δ ( K n 1 K 2 ) 1 = n 1 1 ,故只需证 κ 3 ( K n 1 K 2 ) n 1 1 。令 V ( K n 1 ) = { u 1 , u 2 , , u n 1 } V ( K 2 ) = { v 1 , v 2 } S = { x , y , z } V ( K n 1 K 2 ) 。下面分两种子情形讨论。

子情形2.1: S K n 1 v i i = 1 , 2

不失一般性,假设 S K n 1 v 1 。由定理2.1知, ,故在 K n 1 中有 n 1 2 棵内部不交的S-斯坦纳树,记作 T 1 , T 2 , , T n 1 2 。令 T n 1 1 = T 1 v 2 x x v 2 y y v 2 z z v 2 。显然, T 1 , T 2 , , T n 1 1 n 1 1 棵内部不交的S-斯坦纳树。

子情形2.2:S中的某两个顶点属于某个 K n 1 v i i = 1 , 2

不失一般性,假设 x , y K n 1 v 1 z 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 i n 1 1 ,在 K n 1 v 2 中存在 n 1 1 条内部不交的 x v 2 z -路 Q i 1 i n 1 1 。令 x i 是在 P i 上的x的邻点。令 T i = P i x i v 2 Q i z x i v 2 x i 1 i n 1 1 。显然, T 1 , T 2 , , T n 1 1 n 1 1 棵内部不交的S-斯坦纳树。

情形3: n 1 3 , n 2 3

由引理2.2知, κ 3 ( K n 1 K n 2 ) δ ( K n 1 K n 2 ) 1 = n 1 + n 2 3 ,故只需证 κ 3 ( K n 1 K n 2 ) n 1 + n 2 3 。令 V ( K n 1 ) = { u 1 , u 2 , , u n 1 } V ( K n 2 ) = { v 1 , v 2 , , v n 2 } S = { x , y , z } V ( K n 1 K n 2 ) 。下面分三种子情形讨论。

子情形3.1: S K n 1 v i 1 i n 2

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

子情形3.2:S中的某两个顶点属于某个 K n 1 v i 1 i n 2

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

子情形3.3:S中的三个顶点分别属于不同的 K n 1 v i 1 i n 2

不失一般性,设 x K n 1 v 1 y K n 1 v 2 z K n 1 v 3 。下面分三种情形讨论。

如果 S K n 2 u i ,不妨设 S 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 , , T n 2 2 。令 T i = T 1 u i x x u i y y u i z z u i 2 i n 1 。显然, T 1 , T 2 , , T n 2 2 , T 2 , , T n 1 n 1 + n 2 3 棵内部不交的S-斯坦纳树。

如果 x , y K n 2 u s z K n 2 u t , 其中 s 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 i n 1 1 。因为 K n 1 是简单图,所以在 K n 1 v 1 中可以找到 n 1 2 条长度至少为2的 x z v 1 -路 P i 1 i n 1 2 。令 x i 是在 P i 上的x的邻点, T i = x P i x i x i v 2 P i v 2 y x i v 3 P i v 3 z x i v 2 x i x i v 2 x i v 3 1 i n 1 2 T n 1 1 = P n 1 1 P n 1 1 v 2 z v 1 z v 2 z v 2 z T n 1 = x y y y v 3 P n 1 1 v 3 T j = x v j x x v j y z v j z P 1 v j 4 j n 2 。显然, T 1 , T 2 , , T n 1 , T 4 , , T n 2 n 1 + n 2 3 棵内部不交的S-斯坦纳树。

如果 x K n 2 u r y K n 2 u s z 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 4 n 2 3 时,令 w i 是在图 K n 1 v 1 中除顶点 y v 1 z v 1 外的x的邻点,则 T i = x w i w i w i v 2 w i v 2 w i v 3 w i v 2 y w i v 3 z 1 i n 1 3 。令 T 1 = x y v 1 y v 1 z v 1 y y v 1 z z v 1 T 2 = x x v 2 x v 2 y y z v 2 z v 2 z T 3 = x x v 3 x v 3 y v 3 y v 3 z y v 3 y T j = x x v j y y v j z z v j x v j y v j y v j z v j 4 j n 2 。显然, T 1 , T 2 , , T n 1 3 , T 1 , , T n 2 n 1 + n 2 3 棵内部不交的S-斯坦纳树。

定理3.2:对于任意 k ( k 2 ) 个完全图,有 κ 3 ( K n 1 K n 2 K n k ) = i = 1 k n i k 1

证明:对k用归纳法。因为图的笛卡尔积满足交换律和结合律,所以可设 n 1 n 2 n k 。如果 n k = 2 ,那么 K n 1 K n 2 K n k 是超立方体 Q k ,由定理2.5与引理2.6知,定理成立。

接下来只讨论 n k 3 即可。当 k = 2 时,由定理3.1知,定理成立;假设对于任意不超过 k 1 个完全图的笛卡尔积,定理都成立,即 κ 3 ( K n 1 K n 2 K n k 1 ) = i = 1 k 1 n i k 成立;现在证明对于任意k个完全图的笛卡尔积,定理成立。由引理2.2知, κ 3 ( K n 1 K n 2 K n k ) δ ( K n 1 K n 2 K n k ) 1 = i = 1 k n i k 1 ,故只需证 κ 3 ( K n 1 K n 2 K n k ) i = 1 k n i k 1 。为了简便,令图G表示图 K n 1 K n 2 K n k 1 a = i = 1 k 1 n i k b = i = 1 k n i k 1 。令 V ( G ) = { u 1 , u 2 , , u n } V ( K n k ) = { v 1 , v 2 , , v n k } S = { x , y , z } V ( G K n k ) 。考虑如下三种情形。

情形1: S G v i 1 i n k

不失一般性,假设 S G v 1 。由归纳假设知,在 G v 1 中可以找到a棵内部不交的S-斯坦纳树,记作 T 1 , T 2 , , T a 。我们只需在 G v 1 外找 n k 1 棵内部不交的S-斯坦纳树,令 T i = T 1 v i x x v i y y v i z z v i 2 i n k 。显然, T 1 , T 2 , , T a , T 2 , , T n k 是b棵内部不交的S-斯坦纳树。

情形2:S中的某两个顶点属于某个 G v i 1 i n k

不失一般性,假设 x , y G v 1 z G v 2 。下面分两种子情形讨论。

子情形2.1: | z v 1 { x , y } | = 0

因为 κ ( G ) = δ ( G ) = a + 1 G v i G i = 1 , 2 , , n k ,所以由定理2.3知,在 G v 1 中存在 a + 1 条内部不交的xy-路 P i 1 i a + 1 ,在 G v 2 中存在 a + 1 条内部不交的 x v 2 z -路 Q i 1 i a + 1 。令 x i 是在 P i 上的x的邻点。在 G v j 中任取一棵 { x v j , y v j , z v j } -斯坦纳树 R v j 3 j n k 。令 T i = P i x i v 2 Q i z x i v 2 x i 1 i a + 1 T j = R v j x x v j y y v j z z v j 3 j n k 。显然, T 1 , T 2 , , T a + 1 , T 3 , , T n k 是b棵内部不交的S-斯坦纳树。

子情形2.2: | z v 1 { x , y } | = 1

不失一般性,假设 z v 1 = y 。因为 κ ( G ) = δ ( G ) = a + 1 G v 1 G ,所以由定理2.3知,在中存在 a + 1 条内部不交的xy-路 P i 1 i a + 1 。令 x i 是在 P i 上的x的邻点。令 T i = P i x i v 2 P i v 2 z x i v 2 x i 1 i a + 1 T j = P 1 v j x x v j y y v j z y v j 3 j n k 。显然, T 1 , T 2 , , T a + 1 , T 3 , , T n k 是b棵内部不交的S-斯坦纳树。

情形3:S中的三个顶点分别属于不同的 G v i 1 i n k

不失一般性,假设 x G v 1 y G v 2 z G v 3 。下面分三种子情形讨论。

子情形3.1: S K n k u i 1 i n

不失一般性,假设 S K n k u 1 。因为 κ ( G ) = δ ( G ) = a + 1 ,所以在 G v 1 中,顶点x有 a + 1 个邻点,记作 x 1 , x 2 , , x a + 1 。令 T i = x x i y x i v 2 z x i v 3 x i x i v 2 x i v 2 x i v 3 1 i 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 , , T n k 2 。显然, T 1 , T 2 , , T a + 1 , T 1 , , T n k 2 是b棵内部不交的S-斯坦纳树。

子情形3.2: x , y K n k u s z K n k u t s t

因为 κ ( G ) = δ ( G ) = a + 1 G v 1 G ,所以由定理2.3知,在 G v 1 中存在 a + 1 条内部不交的 x z v 1 -路 P i 1 i a + 1 。因为图G是简单图,所以在 G v 1 中可以找到a条长度至少为2的 x z v 1 -路 P i 1 i a 。令 x i 是在 P i 上的x的邻点。令 T i = x P i x i x i v 2 P i v 2 y x i v 3 P i v 3 z x i v 2 x i x i v 2 x i v 3 1 i a T a + 1 = P a + 1 v 2 x y z z v 2 T a + 2 = x x v 3 y x v 3 P a + 1 v 3 T j = P 1 v j x v j x x v j y z v j z 4 j n k 。显然, T 1 , T 2 , , T a + 2 , T 4 , , T n k 是b棵内部不交的S-斯坦纳树。

子情形3.3: x K n k u i y K n k u l z 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 j a + 1 。假设 u m 不在 P j 上, 1 j a 。由引理2.4知,在G中存在一个从 u m { u i 1 , u i 2 , , u i a , u i } ( a + 1 ) -扇,记作 Q j ,其中有一条 u i j u m -路, 1 j a Q a + 1 是一条 u m u i -路。令 H j = ( u i u i j ) v 1 K n k u i j ( P j u i ) v 2 Q j v 3 1 j a 。因为每个 H j 有一棵支撑树 T j 1 j 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 j n k 1 。又因为 K n k 是完全图,所以可假设 v i 1 , v i 2 , , v i n k 3 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 , , v i n k 3 , v 2 } ( n k 2 ) -扇,记作 S j ,其中有一条 v i j v 3 -路, 1 j n k 3 ,有一条 v 2 v 3 -路 S n k 2 。令 T j = ( R j v 2 ) u i ( G { u i 1 , u i 2 , , u i a } ) v i j ( v i j v 2 ) u l S j u m 1 j n k 3 T n k 2 = ( v 1 v 2 ) u i ( G { u i 1 , u i 2 , , u i a } ) v 2 S n k 2 u m T n k 1 = ( v 1 v 3 ) u i Q a + 1 v 3 P a + 1 v 1 ( v 1 v 2 ) u l 。显然, T 1 , T 2 , , T a , T 1 , , T n k 1 是b棵内部不交的S-斯坦纳树(如图1所示)。

Figure 1. Solid lines in bold for T j , 1 j a ; Solid lines for T j , 1 j n k 3 ; Dashed lines for T n k 2 ; Dashed lines in bold for T n k 1

图1. 粗实线表示 T j 1 j a ;细实线表示 T j , 1 j 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 ) a 1 ,故在 ( G u m ) u i u l 中存在 a 1 条内部不交的 u i u l -路,记作 P j 。令 u i j u i 的邻点, 1 j a 1 。由引理2.4知,在 G u i u l 中存在一个从 u m { u i 1 , u i 2 , , u i a 1 } ( a 1 ) -扇。类似于情况1,可以构造 a 1 棵内部不交的S-斯坦纳树 T 1 , T 2 , , T a 1 。又因为 κ ( K n k ) = n k 1 ,所以可以构造 n k 3 棵内部不交的S-斯坦纳树 T 1 , T 2 , , T n k 3 。显然, T 1 , T 2 , , T a 1 , T 1 , T 2 , , T n k 3 , T 1 , T 2 , T 3 是b棵内部不交的S-斯坦纳树。

基金项目

国家自然科学基金(No. 11401181)。

致谢

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

文章引用:
李恒哲, 芦园园, 王佳佳. 完全图的笛卡尔积的广义3-连通度[J]. 应用数学进展, 2019, 8(2): 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