Search

• We propose some lower and upper bounds for the g -component connectivity along with their sharpness. • We characterize some trees and general graphs with the given g -component connectivity. • We suggest characterizations of graphs with given g -component connectivity and Erdös-Gallai-type problems for the g -component connectivity in this paper. 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. [ABSTRACT FROM AUTHOR]