Structure of tight (k,0)-stable graphs

Abstract

We say that a graph G is $(k,\ell )$-stable if removing $k$ vertices from it reduces its independence number by at most $\ell$. We say that G is tight $(k,\ell )$-stable if it is $(k,\ell )$-stable and its independence number equals $\lfloor \frac{n-k+1}{2}\rfloor +\ell$, the maximum possible, where $n$ is the vertex number of G. Answering a question of Dong and Wu, we show that every tight $(2,0)$-stable graph with odd vertex number must be an odd cycle. Moreover, we show that for all $k\ge 3$, every tight $(k,0)$-stable graph has at most $k+6$ vertices.

7 pages