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 Cet article a éte moissonné depuis la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

Voir la notice de l'article

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 },
     year = {2014},
     volume = {24},
     number = {2},
     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
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
%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/