Retour

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.

, 17 pages

Axe de recherche

Publication

, et
Yugoslav Journal of Operations Research, 24(2), 199–215, 2014 référence BibTeX