Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2401.16639 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929235667451904 |
|---|---|
| author | Dong, Dingding Luo, Sammy |
| author_facet | Dong, Dingding Luo, Sammy |
| contents | We say that a graph G is $(k,\ell)$-stable if removing $k$ vertices from it reduces its independence number by at most $\ell$. We say that G is tight $(k,\ell)$-stable if it is $(k,\ell)$-stable and its independence number equals $\lfloor{\frac{n-k+1}{2}\rfloor}+\ell$, 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\geq 3$, every tight $(k,0)$-stable graph has at most $k+6$ vertices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_16639 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Structure of tight (k,0)-stable graphs Dong, Dingding Luo, Sammy Combinatorics We say that a graph G is $(k,\ell)$-stable if removing $k$ vertices from it reduces its independence number by at most $\ell$. We say that G is tight $(k,\ell)$-stable if it is $(k,\ell)$-stable and its independence number equals $\lfloor{\frac{n-k+1}{2}\rfloor}+\ell$, 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\geq 3$, every tight $(k,0)$-stable graph has at most $k+6$ vertices. |
| title | Structure of tight (k,0)-stable graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2401.16639 |