Relationship between g-extra Connectivity and g-restricted Connectivity in Networks

The fault tolerance of a network can be measured by many parameters. Connectivity is a classic measurement parameter for evaluating the fault tolerance of a network. g-extra connectivity and g-restricted connectivity are generalizations of connectivity, which can better reflect the fault tolerance of a network. Specifically, the g-extra connectivity kappa(g)(G) of a graph G is the minimum number of nodes whose removal will disconnect G, and each remaining component has no less than g + 1 nodes. Furthermore, the g-restricted connectivity kappa(g)(G) of G is the minimum number of nodes whose deletion results in a graph being disconnected and the minimum degree of each remaining component is at least g. In general, g-restricted connectivity is not equal to g-extra connectivity of a network. Therefore, many scholars often discuss g-restricted connectivity and g-extra connectivity with regard to different networks separately. In this paper, we show that g-restricted connectivity is equal to g-extra connectivity under some conditions. Then, the relationship we derived can be applied to some known networks such as the data center networks DCell and BCDC, multiprocessor network (n, k)-star. In addition, we construct a new network H(G0, G1, G2; M) and prove that our result can be applied to it. In detail, we prove kappa(g) (H(G(0), G(1), G(2); M)) = kappa(g)(H(G(0), G(1), G(2); M)) = n + g + 1 for any integers n >= 3 and g <= right perpendicular n-2/ 2 left perpendicular.