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−⌈2√n−1⌉
.
Dans le cas où n
est de la forme a2+1
pour un entier pair a
au
moins égal à 4
, f−t
est au plus égale à
n−⌈2√n−1⌉−1
. 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+1−⌈2√2n⌉
; cette borne aussi est
la meilleure possible.
Paru en septembre 2011 , 17 pages
Axe de recherche
Publication
jan. 2014
, et
Yugoslav Journal of Operations Research, 24(2), 199–215, 2014
référence BibTeX