<  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)

Open Acess document in PolyPublie and at official publisher
[img]
Preview
Open Access to the full text of this document
Published Version
Terms of Use: Creative Commons Attribution Non-commercial Share Alike
Download (184kB)
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

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

Repository Staff Only

View Item View Item