On tight $(k, \ell)$-stable graphs
- Series
- Graph Theory Seminar
- Time
- Tuesday, April 9, 2024 - 15:30 for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Zixia Song – University of Central Florida – zixia.song@ucf.edu
For integers $k>\ell\ge0$, a graph $G$ is $(k,\ell)$-stable if $\alpha(G-S)\geq \alpha(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 $\alpha(G) \le \lfloor ({|V(G)|-k+1})/{2}\rfloor+\ell$. A $(k,\ell)$-stable graph $G$ is tight if $\alpha(G) = \lfloor ({|V(G)|-k+1})/{2}\rfloor+\ell$; and $q$-tight for some integer $q\ge0$ if $\alpha(G) = \lfloor ({|V(G)|-k+1})/{2}\rfloor+\ell-q$.
In this talk, 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. \\
This is joint work with Xiaonan Liu and Zhiyu Wang.