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