Back

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 ft is at most n2n1. In the special case where n is of the form a2+1 for some even integer a4, ft is at most n2n11. 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+122n; this bound is also tight.

, 17 pages

Research Axis

Publication

, , and
Yugoslav Journal of Operations Research, 24(2), 199–215, 2014 BibTeX reference