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 ft est au plus égale à n2n1. Dans le cas où n est de la forme a2+1 pour un entier pair a au moins égal à 4, ft est au plus égale à n2n11. Nous prouvons aussi que ces bornes sont les meilleures possibles pour un graphe G d'ordre n. De plus, si α dénote le nombre de stabilité de G, nous montrons que la différence αt est au plus n+122n; 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