G-2011-45
On the Maximum Orders of an Induced Forest, an Induced Tree, and a Stable Set
, et référence BibTeX
Soit \(G\)
un graphe connexe, \(n\)
l'ordre de \(G\)
, et \(f\)
(resp. \(t\)
)
l'ordre maximum d'une forêt induite (resp. d'un arbre induit) dans
\(G\)
. Dans le présent article nous montrons que la différence \(f-t\)
est au plus égale à \(n - \left \lceil 2 \sqrt{n-1} \right \rceil\)
.
Dans le cas où \(n\)
est de la forme \(a^2+1\)
pour un entier pair \(a\)
au
moins égal à \(4\)
, \(f-t\)
est au plus égale à
\(n - \left \lceil 2 \sqrt{n-1} \right \rceil - 1\)
. Nous prouvons aussi
que ces bornes sont les meilleures possibles pour un graphe \(G\)
d'ordre
\(n\)
. De plus, si \(\alpha\)
dénote le nombre de stabilité de \(G\)
, nous
montrons que la différence \(\alpha - t\)
est au plus
\(n + 1 - \left \lceil 2 \sqrt{2n}\right \rceil\)
; cette borne aussi est
la meilleure possible.
Paru en septembre 2011 , 17 pages