The reliability analysis based on the generalized connectivity in balanced hypercubes.

Recently, network connectivity analysis in terms of reliability has received attention from the network research community. Although traditional connectivity can be used to assess the strength of the connection between two nodes, however, such measures are inadequate for evaluating the connectivity among a set of multiple nodes in a network. Given a set S of vertices in a graph G with | S | ⩾ 2 , we say that a tree in G is an S -tree if it connects all vertices of S. Two S -trees T and T ′ in G are internally disjoint if E (T) ∩ E (T ′) = 0̸ and V (T) ∩ V (T ′) = S. Let κ G (S) denote the maximum number of S -trees in G such that every pair of them are internally disjoint. For an integer k ⩾ 2 , the generalized k -connectivity of graph G is defined as κ k (G) = m i n { κ G (S) ∣ S ⊆ V (G) and | S | = k }. In this paper, we investigate the problem of finding the generalized 3-connectivity of the n -dimensional balanced hypercube B H n , which is a hypercube-variant network and is superior to hypercube due to having a smaller diameter. As a result, we prove that κ 3 (B H n) = 2 n − 1 for n ⩾ 1. [ABSTRACT FROM AUTHOR]