On tight $(k,\ell )$-stable graphs

Abstract

For integers $k>\ell \ge 0$, a graph $G$ is $(k,\ell )$-stable if $\alpha (G-S)\ge \alpha (G)-\ell$ for every $S\subseteq V(G)$ with $|S|=k$. A recent result of Dong and Wu [SIAM J. Discrete Math., 36 (2022) 229--240] shows that every $(k,\ell )$-stable graph $G$ satisfies $\alpha (G)\le \lfloor (|V(G)|-k+1)/2\rfloor +\ell$. A $(k,\ell )$-stable graph $G$ is tight if $\alpha (G)=\lfloor (|V(G)|-k+1)/2\rfloor +\ell$; and $q$-tight for some integer $q\ge 0$ if $\alpha (G)=\lfloor (|V(G)|-k+1)/2\rfloor +\ell -q$. In this paper, we first prove that for all $k\ge 24$, the only tight $(k,0)$-stable graphs are $K_{k+1}$ and $K_{k+2}$, answering a question of Dong and Luo [arXiv: 2401.16639]. We then prove that for all nonnegative integers $k,\ell ,q$ with $k\ge 3\ell +3$, every $q$-tight $(k,\ell )$-stable graph has at most $k-3\ell -3+2^{3(\ell +2q+4{)}^2}$ vertices, answering a question of Dong and Luo in the negative.

11 pages