Groupe d’études et de recherche en analyse des décisions

G-2011-45

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

, et

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

, 17 pages