### G-2011-45

# 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.

Published **September 2011**
,
17 pages