Structure of Tight $(k,0)$-Stable Graphs

Dingding Dong¹ ; Sammy Luo²

¹Harvard University
²Massachusetts Institute of Technology

The electronic journal of combinatorics, Tome 32 (2025) no. 4

Résumé

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\geq3$, every tight $(k,0)$-stable graph has at most $k+6$ vertices.

Détail

DOI : 10.37236/13791