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−⌈2√n−1⌉
. In the
special case where n
is of the form a2+1
for some even integer
a≥4
, f−t
is at most
n−⌈2√n−1⌉−1
. We also prove that
these bounds are tight. In addition, letting α
denote the
stability number of G
, we show that α−t
is at most
n+1−⌈2√2n⌉
; 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