Speaker: 

Dingding Dong

Institution: 

Caltech

Time: 

Monday, May 4, 2026 - 2:00pm to 3:00pm

Host: 

Location: 

340P Rowland Hall

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 ⌊(n−k+1)/2⌋+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≥3, every tight (k,0)-stable graph has at most k+6 vertices. This is joint work with Sammy Luo.