完全对换图的广义3-连通度（英文）  

The Generalized 3-connectivity of Complete-transposition Graphs

作　　者：张燕 阿依古丽.马木提 ZHANG Yan;Aygul Mamut(College of Mathematics and System Sciences,Xinjiang University,830046,Urumqi,Xinjiang,PRC)

机构地区：[1]新疆大学数学与系统科学学院,新疆维吾尔自治区乌鲁木齐市830046

出　　处：《曲阜师范大学学报（自然科学版）》2019年第1期1-6,共6页Journal of Qufu Normal University(Natural Science)

基　　金：Natural Science Foundatoon of China(11361060)

摘　　要：令S■V(G)κ.G(S)表示图G中内部不交的S-树T1,T2,…,Tr的最大数目r,使得对任意i,j∈{1,2,…,r}且i≠j,有V(Ti)∩V(Tj)=S,E(Ti)∩E(Tj)=.定义κk(G)=min{κG(S)|S■V(G),且|S|=k}为图G的广义k-连通度,其中k是整数,且2≤k≤n.完全对换图在网络中是重要的一类Cayley图.该文证明了n-维完全对换图CTn的广义3-连通度是n(n-1)/2-1,也就是说,对于CTn的任意三个点,存在n(n-1)/2-1个连接它们的内部不交的树.Let S■V(G)andκG(S)denote the maximum number r of internally disjoint S-trees T1,T2,…,Tr in graph G such that V(Ti)∩V(Tj)=S and E(Ti)∩E(Tj)=Фfor any i,j∈{1,2,…,r}and i≠j.For an integer k with 2≤k≤n,the generalized k-connectivity of a graph G is defined asκk(G)=min{κG(S)|S■V(G)and|S|=k}.Complete-transposition graphs are a class of important Cayley graphs in networks.This paper shows that the generalized 3-connectivity of an n-dimensional complete-transposition graph CTn is n(n-1)/2-1,that is,for any three vertices in CT n,there exist n(n-1)/2-1 internally disjoint trees connecting them in CTn.

关 键 词：完全对换图 广义连通度 内部不交的S-树 邻点 

分 类 号：O157.6[理学—数学]