The Generalized 3-Connectivity of Exchanged Folded Hypercubes

Abstract

For S⊆V(G),κG(S) denotes the maximum number k of edge disjoint trees T1,T2,…,Tk in G, such that V(Ti)∩V(Tj)=S for any i,j∈{1,2,…,k} and i≠j. For an integer 2≤r≤|V(G)|, the generalized r-connectivity of G is defined as κr(G)=min{κG(S)|S⊆V(G)and|S|=r}. In fact, κ2(G) is the traditional connectivity of G. Hence, the generalized r-connectivity is an extension of traditional connectivity. The exchanged folded hypercube EFH(s,t), in which s≥1 and t≥1 are positive integers, is a variant of the hypercube. In this paper, we find that κ3(EFH(s,t))=s+1 with 3≤s≤t.

Keywords

• exchanged folded hypercubes
• generalized 3-connectivity
• fault tolerance
• interconnection networks