Dingding Dong : Structure of tight (k,0)-stable graphs

Posted by Vishesh Jain , part of the Mathematical Computer Science Seminar.

At

March 2, 2026, 3 p.m.

In

1227 SEO

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.