Cluster connectivity of hypercube-based networks under the super fault-tolerance condition

Abstract The connectivity of a graph G , κ ( G ) , is the minimum cardinality over all vertex-cuts in G , and the value of κ ( G ) can be determined using Menger’s theorem. It has long been one of the most important factors that characterize both graph reliability and fault tolerability. A graph G is super connected if its minimum vertex-cut is always composed of a vertex’s neighborhood. In this article we define the super H -connectivity κ ′ ( G | H ) and the super H ∗ -connectivity κ ′ ( G | H ∗ ) as new measures to evaluate the connectedness of G , for which H denotes a connected graph that represents the structure of the clustered faults, and H ∗ denotes the union of the set of all connected subgraphs of H and the set of the trivial graph. Then we establish both κ ′ ( Q n | H ) and κ ′ ( Q n | H ∗ ) for H ∈ { K 1 , m ∣ m = 1 , 2 , 3 , 4 } ∪ { P 4 , C 4 } , where Q n denotes the n -dimensional hypercube, K 1 , m denotes the m -star structure for m ≥ 1 , P 4 denotes a path of order four and C 4 is a cycle of order four.