On the Maximum Orders of an Induced Forest, an Induced Tree, and a Stable Set


Alain Hertz, Odile Marcotte, David Schindl




Let $G$ be a connected graph, $n$ the order of $G$, and $f$ (resp. $t$) the maximum order of an induced forest (resp. tree) in $G$. We show that $f-t$ is at most $n - \lceil 2\sqrt{n-1} \rceil.$ In the special case where $n$ is of the form $a^2 + 1$ for some even integer $a \geq 4$, $f-t$ is at most $n - \lceil 2\sqrt{n-1} \rceil - 1.$ We also prove that these bounds are tight. In addition, letting $\alpha$ denote the stability number of $G$, we show that $\alpha - t$ is at most $n + 1 - \lceil 2\sqrt{2n} \rceil;$this bound is also tight.