In this article, we study the relationship between three invariants of undirected graphs: the maximum order of an induced forest, the stability number, and the maximum order of an induced tree. Although bounds on invariants such as these have been studied for a long time by graph theorists, the past few years have seen a surge of interest in the systematic study of linear relations (or other kinds of relations) between graph invariants. | Yugoslav Journal of Operations Research 24 (2014) Number 2, 199-215 DOI: ON THE MAXIMUM ORDERS OF AN INDUCED FOREST, AN INDUCED TREE, AND A STABLE SET Alain HERTZ D´epartement de math´ematiques et g´enie industriel ´ Ecole Polytechnique de Montr´eal . 6079, succ. Centre-ville, Montr´eal, Canada H3C 3A7 Odile MARCOTTE GERAD, HEC Montr´eal and D´epartement d’informatique, UQAM 3000 Cˆote-Sainte-Catherine, Montr´eal, Canada H3T 2A7 David SCHINDL ´ Haute Ecole de gestion de Gen`eve Campus Battelle - Bˆatiment F 7, route de Drize, 1227 Carouge, Suisse Received: April 2013 / Accepted: September 2013 Abstract: 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. Keywords: Induced forest, induced tree, stability number, extremal graph theory. MSC: 05C05, 05C35, 05C69. 1 INTRODUCTION In this article, we study the relationship between three invariants of undirected graphs: the maximum order of an induced forest, the stability number, and the maximum order of an induced tree. Although bounds on invariants such as 200 A. Hertz, O. Marcotte, D. Schindl / On The Maximum Orders these have been studied for a long time by graph theorists, the past few years have seen a surge of interest in the systematic study of linear relations (or other kinds of relations) between graph invariants. We focus our attention on the difference between the maximum order of an induced forest and the maximum order of an induced tree; also, we give an upper bound on this difference, and prove that it is tight. A similar but simpler proof .
