{"id":"arxiv/2608.17945","url":"https://arxiv.org/abs/2608.17945","tags":["math.CO"],"score":0,"title":"A characterization of tight ($ k, 0 $)-stable graphs","domain":"math.CO","source":"arxiv","authors":["Yuqi Xu","Weihua Yang","Xiaxia Guan"],"reviews":0,"subject":"math.CO","summary":"Let k and l be two non-negative integers with k > l. A graph G is (k,l)-stable if alpha(G - S) >= alpha(G) - l for every subset S of V(G) with |S| = k, where alpha(G) denotes the independence number of G. Dong and Wu established that alpha(G) = 4. In particular, we prove that tight (k, 0)-stable graphs are K_{k+1} and K_{k+2} for k >= 5, which not only extends the result of Liu, Song and Wang [J. Graph Theory 110(2) (2025), 193-199] from k >= 24 to k >= 5, but also proves the conjecture of Dong and Luo [Electron. J. Comb. 32(4) (2025), 4-45] once more.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-18","reactions":{}}