On the maximum orders of an induced forest, an induced tree, and a stable set

Alain Hertz, Odile Marcotte, David Schindl

Article de revue (2014)

Accéder à ce document
Disponible
Libre accès au texte intégral dans PolyPublie et chez l'éditeur officiel
Version officielle de l'éditeur
Texte Texte • 184kB •
Voir dans PolyPublie
Voir chez l'éditeur officiel

Résumé

Let G be a connected graph, n the order of G, and f (resp. t) the maximum order of an induced forest (resp. tree) in G. We show that f − t is at most n − ⌠2√n − 1⌡ . In the special case where n is of the form a² + 1 for some even integer a ≥ 4, f − t is at most n − ⌠2√n − 1⌡ − 1. We also prove that these bounds are tight. In addition, letting α denote the stability number of G, we show that α − t is at most n + 1 − ⌠2√2n⌡; this bound is also tight.

Mots clés

Département:
Département de mathématiques et de génie industriel
Unité de recherche:
GERAD - Groupe d'études et de recherche en analyse des décisions
Adresse URL de PolyPublie:
https://publications.polymtl.ca/3626/
Titre de la revue :
Yugoslav Journal of Operations Research ( vol. 24 , no 2 )
Maison d'édition:
Faculty of Organizational Sciences, Belgrade, Mihajlo Pupin Institute, Belgrade, Faculty of Transport and Traffic Engineering, Belgrade, Faculty of Mining and Geology – Department of Mining, Belgrade, Mathematical Institute SANU, Belgrade
DOI:
10.2298/yjor130402037h
URL officielle:
https://doi.org/10.2298/yjor130402037h
OAI:
oai:publications.polymtl.ca:3626
ORCID
Date du dépôt:
09 mars 2020 13:32
Dernière modification:
14 oct. 2026 10:42
Citer en APA 7:
Hertz, A., Marcotte, O., & Schindl, D. (2014). On the maximum orders of an induced forest, an induced tree, and a stable set. Yugoslav Journal of Operations Research, 24(2), 199-215. https://doi.org/10.2298/yjor130402037h

Statistiques

Total des téléchargements à partir de PolyPublie

Téléchargements par année

Provenance des téléchargements

Dimensions

Actions réservées au personnel

Afficher document
Afficher document