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.
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/
@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 -