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

DOI10.1002/JGT.22361MaRDI QIDQ4646949zbMATH OpenOpenAlexWikidataFDO

Authors Tom Kelly, Chun-Hung Liu

Publication date 3 January 2019

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

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

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)

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.

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

Cited in

(8)

• Cycle isolation of graphs with small girth
• Large induced forests in planar graphs with girth 4
• Lower Bounds For Induced Forests in Cubic Graphs
• 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

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)