Geodesic
On the Maximum Orders of an Induced Forest, an Induced Tree, and a Stable Set
Yugoslav journal of operations research, Tome 24 (2014) no. 2, p. 199

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

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 - \lceil 2\sqrt{n-1} \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 - \lceil 2\sqrt{n-1} \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 - \lceil 2\sqrt{2n} \rceil;$this bound is also tight.
Keywords: Induced forest, induced tree, stability number, extremal graph theory. 
@article{YJOR_2014_24_2_a2,
     author = {Alain Hertz and Odile Marcotte and David Schindl},
     title = {On the {Maximum} {Orders} of an {Induced} {Forest,} an {Induced} {Tree,} and a {Stable} {Set}},
     journal = {Yugoslav journal of operations research},
     pages = {199 },
     publisher = {mathdoc},
     volume = {24},
     number = {2},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/YJOR_2014_24_2_a2/}
}
TY  - JOUR
AU  - Alain Hertz
AU  - Odile Marcotte
AU  - David Schindl
TI  - On the Maximum Orders of an Induced Forest, an Induced Tree, and a Stable Set
JO  - Yugoslav journal of operations research
PY  - 2014
SP  - 199 
VL  - 24
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/YJOR_2014_24_2_a2/
LA  - en
ID  - YJOR_2014_24_2_a2
ER  - 
%0 Journal Article
%A Alain Hertz
%A Odile Marcotte
%A David Schindl
%T On the Maximum Orders of an Induced Forest, an Induced Tree, and a Stable Set
%J Yugoslav journal of operations research
%D 2014
%P 199 
%V 24
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/YJOR_2014_24_2_a2/
%G en
%F YJOR_2014_24_2_a2
Alain Hertz; Odile Marcotte; David Schindl. On the Maximum Orders of an Induced Forest, an Induced Tree, and a Stable Set. Yugoslav journal of operations research, Tome 24 (2014) no. 2, p. 199 . http://geodesic.mathdoc.fr/item/YJOR_2014_24_2_a2/