On the g-component connectivity of hypercube-like networks. Issue 2 (4th March 2023) - Yin, Shanshan; Xu, Liqiong; Yu, Zhecheng
Abstract : Reliability evaluation of interconnection networks is of significant importance to the design and maintenance of interconnection networks. The component connectivity is an important parameter for the reliability evaluation of interconnection networks and is a generalization of the traditional connectivity. Let g ≥ 0 be an integer and G be a connected graph. A g -component cut of G is a vertex set S such that G − S has at least g components. The g -component connectivity c κ g ( G ) of G is the size of the smallest g -component cut. Determining the g -component connectivity is still an unsolved problem in many interconnection networks. In this paper, we prove the lower bound of the g -component connectivity of any n -dimensional hypercube-like networks. We also determine the g -component connectivity of varietal hypercubes and crossed cubes which are the members of hypercube-like networks. As a by-product, we characterize the optimal g -component cut under the condition that any two vertices have exactly two common neighbors if they have of any n -dimensional hypercube-like networks.