Group for Research in Decision Analysis

G-2011-45

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

, , and

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