Extremal graphs having no stable cutset (Q1953420): Difference between revisions

Summary: A stable cutset in a graph is a stable set whose deletion disconnects the graph. It was conjectured by \textit{Y. Caro} [\textit{Y. Caro} and \textit{R. Yuster}, Graphs Comb. 15, No. 1, 5--19 (1999; Zbl 0937.05063)] and proved by \textit{G. Chen} and \textit{X. Yu} [Discrete Math. 249, No. 1--3, 41--43 (2002; Zbl 0991.05079)] that any graph with \(n\) vertices and at most \(2n-4\) edges contains a stable cutset. The bound is tight, as we will show that all graphs with \(n\) vertices and \(2n-3\) edges without stable cutset arise recursively glueing together triangles and triangular prisms along an edge or triangle. As a by-product, an algorithmic implication of our result will be pointed out.