2024/04/02 by Liu, Xiaonan, Song, Zi-Xia, Wang, Zhiyu
#05C69 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2404.01639
For integers k>ℓ≥0, a graph G is (k,ℓ)-stable if α(G-S)≥ α(G)-ℓ for every S⊆ V(G) with |S|=k. A recent result of Dong and Wu [SIAM J. Discrete Math., 36 (2022) 229--240] shows that every (k,ℓ)-stable graph G satisfies α(G) ≤ \lfloor (|V(G)|-k+1)/2\rfloor+ℓ. A (k,ℓ)-stable graph G is tight if α(G) = \lfloor (|V(G)|-k+1)/2\rfloor+ℓ; and q-tight for some integer q≥0 if α(G) = \lfloor (|V(G)|-k+1)/2\rfloor+ℓ-q. In this paper, we first prove that for all k≥ 24, the only tight (k, 0)-stable graphs are Kk+1 and Kk+2, answering a question of Dong and Luo [arXiv: 2401.16639]. We then prove that for all nonnegative integers k, ℓ, q with k≥ 3ℓ+3, every q-tight (k,ℓ)-stable graph has at most k-3ℓ-3+23(ℓ+2q+4)2 vertices, answering a question of Dong and Luo in the negative.