The Generalized 4‐Connectivity of Cube‐Connected‐Cycle and Hierarchical Hypercube

The connectivity is an important measurement for the fault tolerance of a network. Let G = (V(G), E(G)) be a connected graph with the vertex set V(G) and edge set E(G). An S‐tree of graph G is a tree T that contains all the vertices in S subject to S⊆V(G). Two S‐trees T and T′ are internally disjoint if and only if E(T)∩E(T′) = ∅ and V(T)∩V(T′) = S. Denote κG(S) by the maximum number of internally disjoint S‐trees in graph G. The generalized k‐connectivity is a natural generalization of the classical connectivity, which is defined as κr(G) = min{κG(S)|S⊆V(G)and|S| = r}. In this paper, we mainly focus on the generalized connectivity of cube‐connected‐cycle CCCn and hierarchical hypercube HHCn, which were introduced for massively parallel systems. We show that for n = 2m + 2(m ≥ 1), κ4(HHCn) = m and κ4(CCCn) = 2, that is, for any four vertices in CCCn (or HHCn), there exist 2 (or m) internally disjoint S‐trees connecting them in CCCn (or HHCn).