On \((K_{q},k)\) stable graphs with small \(k\) (Q456306)

Summary: A graph \(G\) is \((K_{q},k)\) stable if it contains a copy of \(K_{q}\) after deleting any subset of \(k\) vertices. In a previous paper we have characterized the \((K_q,k)\) stable graphs with minimum size for \(3 \leq q \leq 5\) and we have proved that the only \((K_q,k)\) stable graph with minimum size is \(K_{q+k}\) for \(q \geq 5\) and \(k \leq 3\). We show that for \(q \geq 6\) and \(k \leq \frac{q}{2}+1\) the only \((K_q,k)\) stable graph with minimum size is isomorphic to \(K_{q+k}\).