Measuring the vulnerability for classes of intersection graphs (Q1364473)

Edge connectivity is a very studied parameter in graph theory which measures the vulnerability of a graph (i.e. the resistance of the graph to deletions of vertices or edges). But there are other parameters of interest. For example, if the binding number of a graph is at least \(3/2\), then the existence of a Hamiltonian circuit is guaranted. In this paper, the authors focus on three previously introduced parameters, namely the thoughness (introduced by Chvátal in 1973), the scattering number (introduced by Jung in 1978) and the vertex integrity (introduced by Barefoot in 1987). From an algorithmic point of view, this paper shows that these three parameters can be compared efficiently for many important graph classes. The minimum balanced separator problem is also considered. The authors exhibit polynomial time algorithms which compute exactly a balanced separator of minimum cardinality for special graphs. The algorithms exhibited here compute component number vectors and maximum component order vectors which give information on the vulnerability of graphs. In conclusion, the authors detail how the approach developed in this paper for trapezoid graphs can be generalized to other classes of intersection graphs.