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

The Generalized 3-connectivity of Complete-transposition Graphs

令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.