On the maximum induced forests of a connected cubic graph without triangles

DOI10.1016/0012-365X(90)90165-EMaRDI QIDQ757394zbMATH OpenFDO

Authors Maolin Zheng, Xiaoyun Lu

Publication date 1990

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(90)90165-E

zbMATH Keywords

cubic graphinduced forest

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35)

Review text

Let t(G) denote the cardinality of a maximum induced forest of a graph G with n vertices. This paper proves that t(G)\(\geq \frac{2n}{3}\) for any cubic graph G without triangles, except for two cubic graphs with \(n=8\) and \(t(G)=5\). This lower bound is best possible and implies that Speckenmeyer's conjecture is true with two exceptions.

Recommendations

• Induced forests in cubic graphs
• Lower Bounds For Induced Forests in Cubic Graphs
• On maximum induced forests in graphs
• An improved bound on the largest induced forests for triangle-free planar graphs
• A better bound on the largest induced forests in triangle-free planar graph
• Large induced forests in triangle-free planar graphs
• Maximum induced forests of planar graphs
• Maximum induced forests in graphs of bounded treewidth
• A lower bound on the order of the largest induced linear forest in triangle-free planar graphs
• Induced trees in triangle-free graphs

Cites work

• scientific article; zbMATH DE number 3480616 (Why is no real title available?)
• Induced forests in cubic graphs
• Lower Bounds For Induced Forests in Cubic Graphs
• On feedback vertex sets and nonseparating independent sets in cubic graphs
• On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three

Cited in

(14)

• Maximum genus and maximum nonseparating independent set of a 3-regular graph
• The integrity of a cubic graph
• A new bound on the feedback vertex sets in cubic graphs
• Feedback vertex sets in cubic multigraphs
• Partial DP-coloring of graphs
• A feedback vertex set of 2-degenerate graphs
• Lower Bounds For Induced Forests in Cubic Graphs
• Size of the largest induced forest in subcubic graphs of girth at least four and five
• The k-conversion number of regular graphs
• A lower bound on the \(k\)-conversion number of graphs of maximum degree \(k+1\)
• Subgraph-avoiding minimum decycling sets and \(k\)-conversion sets in graphs
• Some bounds on the size of maximum G-free sets in graphs
• Upper-embeddability and the decycling number of connected 4-regular graphs
• Induced forests in cubic graphs

This page was built for publication: On the maximum induced forests of a connected cubic graph without triangles

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