G-2011-45
On the Maximum Orders of an Induced Forest, an Induced Tree, and a Stable Set
, , and
BibTeX referenceLet \(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
Research Axis
Publication
Jan 2014
, , and
Yugoslav Journal of Operations Research, 24(2), 199–215, 2014
BibTeX reference