Groupe d’études et de recherche en analyse des décisions

G-2011-45

On the Maximum Orders of an Induced Forest, an Induced Tree, and a Stable Set

, et

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.

, 17 pages