The g-Component Edge Connectivity of Graphs

Connectivity is a classic measure that evaluates the fault tolerance of multiprocessor systems when processor failures occur. To better evaluate the reliability of multiprocessor systems, researchers have proposed many indicators based on connectivity with additional constraints, for example the number of components formed by removing an edge subset or a vertex subset. If the subgraph obtained from G by deleting an edge subset contains at least g components, the minimum size among all such edge subsets is denoted by the g-component edge connectivity of G. Regarding the g-component edge connectivity of many well-known networks, numerous results exist. However, we are particularly interested in general graphs. In this paper, we first establish basic properties of g-component edge connectivity and determine its exact value for complete graphs, paths, cycles and complete multipartite graphs. We then characterize graphs achieving a given g-component edge connectivity. Finally, we study three parameters related to g-component edge connectivity inspired by classical extremal problems.