On $(K_{q},k)$ Stable Graphs with Small $k$

Abstract

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 \le q \le 5$ and we have proved that the only $(K_q,k)$ stable graph with minimum size is $K_{q+k}$ for $q \ge 5$ and $k \le 3$. We show that for $q \ge 6$ and $k \le \frac{q}{2}+1$ the only $(K_q,k)$ stable graph with minimum size is isomorphic to $K_{q+k}$.