Disconnecting graphs by removing vertices: a polyhedral approach

In this paper, we consider the problem of disconnecting a graph by removing as few vertices as possible, such that no component of the disconnected graph has more than a given number of vertices. We give applications of this problem, present a formulation for it, and describe some polyhedral results. Furthermore, we establish ties with other polytopes and show how these relations can be used to obtain facets of our polytope. Finally, we give some computational results.