The g-component connectivity of graphs
He Li, Shumin Zhang, Chengfu Ye, Shuming Zhou · Theoretical Computer Science · 2021
Connectivity is a classic metric to evaluate reliability of multiprocessor system under the circumstances of processor failures. Based on connectivity, more refined quantitative indicators for fault tolerance of multiprocessor system have been extensively explored. The g-component connectivity of a graph G, denoted by cκg(G), is the minimum number of vertices whose removal from G results in a disconnected graph with at least g-components. So far, the values of the g-component (edge) connectivity of special networks with small g have been extensively investigated. For general graphs, the results of the g-component connectivity are very few. In this paper, we propose some lower and upper bounds for the g-component connectivity along with their sharpness, and then suggest some characterization of trees and general graphs with given g-component connectivity. Furthermore, we fix some related extremal problems.