Alain Hertz, Odile Marcotte and David Schindl
Article (2014)
|
Open Access to the full text of this document Published Version Terms of Use: Creative Commons Attribution Non-commercial Share Alike Download (184kB) |
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
Subjects: |
2900 Pure mathematics > 2911 Set theory and general topology 2950 Applied mathematics > 2950 Applied mathematics |
---|---|
Department: | Department of Mathematics and Industrial Engineering |
Research Center: | GERAD - Research Group in Decision Analysis |
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 |
DOI: | 10.2298/yjor130402037h |
Official URL: | https://doi.org/10.2298/yjor130402037h |
Date Deposited: | 09 Mar 2020 13:32 |
Last Modified: | 07 May 2025 08:57 |
Cite in 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 |
---|---|
Statistics
Total downloads
Downloads per month in the last year
Origin of downloads
Dimensions