Group for Research in Decision Analysis

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

## Odile Marcotte, Alain Hertz, and 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 - \left \lceil 2 \sqrt{n-1} \right \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 - \left \lceil 2 \sqrt{n-1} \right \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 - \left \lceil 2 \sqrt{2n}\right \rceil$$; this bound is also tight.

, 17 pages