G-2011-45
On the Maximum Orders of an Induced Forest, an Induced Tree, and a Stable Set
, et
référence BibTeXSoit \(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