Mathematical Computer Science Seminar
Dingding Dong
California Institute of Technology
Structure of tight (k,0)-stable graphs
Abstract: We say that a graph $G$ is $(k,l)$-stable if removing $k$ vertices from it reduces its
independence number by at most $l$. We say that $G$ is tight $(k,l)$-stable if it is
$(k,l)$-stable and its independence number equals $\lfloor(n-k+1)/2\rfloor+l$, 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. This is joint work with Sammy Luo.
Monday March 2, 2026 at 3:00 PM in 1227 SEO