折叠超立方体的广义3-连通度

Generalized 3-connectivity of folded hypercubes

设图G是一个连通图,S⊆V(G)。图G的一棵S-斯坦纳树是一棵包含S中所有顶点的树T=(V′,E′),使得S⊆V′。如果连接S的两棵斯坦纳树T和T′,满足E(T)∩E(T′)=Φ且V(T)∩V(T′)=S,则称T和T′是内部不交的。定义κ(S)为图G中内部不相交S-斯坦纳树的最大数目。广义k-连通度(2≤k≤n)定义为κ_(k)(G)=min{κ(S)|S⊆V(G)且|S|=k},显然,κ_(2)(G)=κ(G)。证明了κ_(3)(FQ_(n))=n,其中FQ_(n)是n-维折叠超立方体。

Let G be a connected graph and S⊆V(G).T=(V′,E′)is an S-Steiner tree which containing all the vertices in is S of G and make S⊆V′.Two S-trees T and T′are said to be internally disjoint if E(T)∩E(T′)=Φ and V(T)∩V(T′)=S.κ(S)is defined as the maximum number of the internally disjoint S-trees in G.The generalized k-connectivity(2≤k≤n)κk(G)of G is defined as κ_(k)(G)=min{κ(S)|S⊆V(G)and|S|=k}.Clearly,κ_(2)(G)=κ(G).κ_(3)(FQ_(n))=n is proved where FQ_(n)is n-dimensional folded hypercube.