<  Back to the Polytechnique Montréal portal

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

Alain Hertz, Odile Marcotte and David Schindl

Article (2014)

Published Version
Terms of Use: Creative Commons Attribution Non-commercial Share Alike.
Download (240kB)
Cite this document: 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), p. 199-215. doi:10.2298/yjor130402037h
Show abstract Hide abstract


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.

Uncontrolled Keywords

Induced forest; induced tree; stability number; extremal graph theory

Open Access document in PolyPublie
Subjects: 2900 Mathématiques pures > 2911 Théorie des ensembles et topologie générale
2950 Mathématiques appliquées > 2950 Mathématiques appliquées
Department: Département de mathématiques et de génie industriel
Research Center: GERAD - Groupe d'études et de recherche en analyse des décisions
Date Deposited: 09 Mar 2020 13:32
Last Modified: 10 Mar 2020 01:20
PolyPublie URL: https://publications.polymtl.ca/3626/
Document issued by the official publisher
Journal Title: Yugoslav Journal of Operations Research (vol. 24, no. 2)
Publisher: 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
Official URL: https://doi.org/10.2298/yjor130402037h


Total downloads

Downloads per month in the last year

Origin of downloads


Repository Staff Only