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

The Generalized 3-Connectivity of Cartesian Product of Complete Graphs

作　　者：李恒哲 芦园园 王佳佳[1] 

机构地区：[1]河南师范大学数学和信息科学学院,河南新乡

出　　处：《应用数学进展》2019年第2期320-326,共7页Advances in Applied Mathematics

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

摘　　要：设S是图G中至少有2个顶点的集合,T是G的一棵子树。如果S?V(T),则称T是G的一棵S-斯坦纳树。设T1与T2是S-斯坦纳树,如果E(T1)∩E(T2)=?且V(T1)∩V(T2)=S,则称T1与T2是内部不交的S-斯坦纳树。KG(S)表示图G中内部不交的S-斯坦纳树的最大数目,KK(G)是当S遍及V(G)的所有k元子集时的最小的KG(S)。在本文中,我们研究完全图的笛卡尔积的K3-连通度。对于任意两个完全图Kn1与Kn2,确定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.

关 键 词：完全图 K₃-连通度 笛卡尔积 

分 类 号：O1[理学—数学]