Size of the largest induced forest in subcubic graphs of girth at least four and five

DOI10.1002/JGT.22361zbMATH Open1473.05144arXiv1603.03855OpenAlexW2963809247WikidataQ129906759 ScholiaQ129906759MaRDI QIDQ4646949FDOQ4646949

Authors: Tom Kelly, Chun-Hung Liu 

Publication date: 3 January 2019

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: In this paper, we address the maximum number of vertices of induced forests in subcubic graphs with girth at least four or five. We provide a unified approach to prove that every 2-connected subcubic graph on $n$ vertices and $m$ edges with girth at least four or five, respectively, has an induced forest on at least $n-frac29m$ or $n-frac15m$ vertices, respectively, except for finitely many exceptional graphs. Our results improve a result of Liu and Zhao and are tight in the sense that the bounds are attained by infinitely many 2-connected graphs. Equivalently, we prove that such graphs admit feedback vertex sets with size at most $frac29m$ or $frac15m$, respectively. Those exceptional graphs will be explicitly constructed, and our result can be easily modified to drop the 2-connectivity requirement.

Full work available at URL: https://arxiv.org/abs/1603.03855

Recommendations

• A lower bound on the order of the largest induced forest in planar graphs with high girth
• Lower Bounds For Induced Forests in Cubic Graphs
• On the maximum induced forests of a connected cubic graph without triangles
• scientific article; zbMATH DE number 9665
• The forest number in several classes of regular graphs
• Feedback vertex sets in cubic multigraphs
• Minimum size of feedback vertex sets of planar graphs of girth at least five
• On the maximum orders of an induced forest, an induced tree, and a stable set
• On feedback vertex sets and nonseparating independent sets in cubic graphs
• Exact Computation of Maximum Induced Forest

zbMATH Keywords

subcubic graphsinduced forestsfeedback vertex-sets

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Distance in graphs (05C12) Graph operations (line graphs, products, etc.) (05C76)

Cited In (8)

• Lower Bounds For Induced Forests in Cubic Graphs
• Large induced forests in planar graphs with girth 4
• Induced forests in some distance-regular graphs
• A better bound on the largest induced forests in triangle-free planar graph
• Maximum induced forests of product graphs
• The size of graphs with given feedback vertex number
• Induced forests in cubic graphs
• Cycle isolation of graphs with small girth

This page was built for publication: Size of the largest induced forest in subcubic graphs of girth at least four and five

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4646949)