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
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
![]() |
|
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: | 08 Apr 2021 10:43 |
PolyPublie URL: | https://publications.polymtl.ca/3626/ |
![]() |
|
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 |
Statistics
Total downloads
Downloads per month in the last year
Origin of downloads
Dimensions