Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2404.01639 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913295523381248 |
|---|---|
| author | Liu, Xiaonan Song, Zi-Xia Wang, Zhiyu |
| author_facet | Liu, Xiaonan Song, Zi-Xia Wang, Zhiyu |
| contents | For integers $k>\ell\ge0$, a graph $G$ is $(k,\ell)$-stable if $α(G-S)\geq α(G)-\ell$ for every $S\subseteq V(G)$ with $|S|=k$. A recent result of Dong and Wu [SIAM J. Discrete Math., 36 (2022) 229--240] shows that every $(k,\ell)$-stable graph $G$ satisfies $α(G) \le \lfloor ({|V(G)|-k+1})/{2}\rfloor+\ell$. A $(k,\ell)$-stable graph $G$ is tight if $α(G) = \lfloor ({|V(G)|-k+1})/{2}\rfloor+\ell$; and $q$-tight for some integer $q\ge0$ if $α(G) = \lfloor ({|V(G)|-k+1})/{2}\rfloor+\ell-q$. In this paper, we first prove that for all $k\geq 24$, the only tight $(k, 0)$-stable graphs are $K_{k+1}$ and $K_{k+2}$, answering a question of Dong and Luo [arXiv: 2401.16639]. We then prove that for all nonnegative integers $k, \ell, q$ with $k\geq 3\ell+3$, every $q$-tight $(k,\ell)$-stable graph has at most $k-3\ell-3+2^{3(\ell+2q+4)^2}$ vertices, answering a question of Dong and Luo in the negative. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_01639 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On tight $(k,\ell)$-stable graphs Liu, Xiaonan Song, Zi-Xia Wang, Zhiyu Combinatorics 05C69 For integers $k>\ell\ge0$, a graph $G$ is $(k,\ell)$-stable if $α(G-S)\geq α(G)-\ell$ for every $S\subseteq V(G)$ with $|S|=k$. A recent result of Dong and Wu [SIAM J. Discrete Math., 36 (2022) 229--240] shows that every $(k,\ell)$-stable graph $G$ satisfies $α(G) \le \lfloor ({|V(G)|-k+1})/{2}\rfloor+\ell$. A $(k,\ell)$-stable graph $G$ is tight if $α(G) = \lfloor ({|V(G)|-k+1})/{2}\rfloor+\ell$; and $q$-tight for some integer $q\ge0$ if $α(G) = \lfloor ({|V(G)|-k+1})/{2}\rfloor+\ell-q$. In this paper, we first prove that for all $k\geq 24$, the only tight $(k, 0)$-stable graphs are $K_{k+1}$ and $K_{k+2}$, answering a question of Dong and Luo [arXiv: 2401.16639]. We then prove that for all nonnegative integers $k, \ell, q$ with $k\geq 3\ell+3$, every $q$-tight $(k,\ell)$-stable graph has at most $k-3\ell-3+2^{3(\ell+2q+4)^2}$ vertices, answering a question of Dong and Luo in the negative. |
| title | On tight $(k,\ell)$-stable graphs |
| topic | Combinatorics 05C69 |
| url | https://arxiv.org/abs/2404.01639 |