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

Abstract

The connectivity is an important measurement for the fault tolerance of a network. Let G=VG,EG be a connected graph with the vertex set VG and edge set EG. An S-tree of graph G is a tree T that contains all the vertices in S subject to S⊆VG. Two S-trees T and T′ are internally disjoint if and only if ET∩ET′=∅ and VT∩VT′=S. Denote κGS 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 κrG=minκGS|S⊆VGandS=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+2m≥1, κ4HHCn=m and κ4CCCn=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).