The 4-Set Tree Connectivity of Folded Hypercube.

The k-set tree connectivity, as a natural extension of classical connectivity, is a very important index to evaluate the fault-tolerance of interconnection networks. Let G = (V,E) be a connected graph and a subset S ⊆ V, an S-tree of graph G is a tree T = (V′,E′) that contains all the vertices of S and E(T) ⊆ E(G). Two S-trees T and T′ are internally disjoint if and only if E(T) ∩ E(T′) = ∅ and V (T) ∩ V (T′) = S. The cardinality of maximum internally disjoint S-trees is defined as κG(S), and the k-set tree connectivity is defined by κk(G) =min{κG(S)|S ⊆ V (G) and |S| = k}. In this paper, we show that the k-set tree connectivity of folded hypercube when k = 4, that is, κ4(FQn) = n, where FQn is folded hypercube for n ≥ 2. [ABSTRACT FROM AUTHOR]