Induced forests in cubic graphs

DOI10.1016/0012-365X(84)90115-8MaRDI QIDQ791532zbMATH OpenFDO

Authors William Staton

Publication date 1984

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(84)90115-8

zbMATH Keywords

cubic graphforestgirthindependence ratio

Mathematics Subject Classification ID

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

Review text

Let G be a graph with vertex set V(G). Denote \(f(G)=\max \quad \{| A| /| V(G)|;A\subset V(G),\) A induces a fores\(t\}\). The author derives bounds on f(G) and consequently calculates that lim \(\inf_{n\to \infty}\{f(G)\); G is a cubic graph with girth at least \(n\}\) equals to 3/4.

Recommendations

• Lower Bounds For Induced Forests in Cubic Graphs
• On the maximum induced forests of a connected cubic graph without triangles
• Size of the largest induced forest in subcubic graphs of girth at least four and five
• On the number of forests and connected spanning subgraphs
• Large induced forests in graphs

Cites work

• Girth and Independence Ratio
• scientific article; zbMATH DE number 3480616 (Why is no real title available?)
• scientific article; zbMATH DE number 3490998 (Why is no real title available?)
• On the independence ratio of a graph
• The Independence Ratio of Regular Graphs
• The point-arboricity of a graph

Cited in

(13)

• Maximum genus and maximum nonseparating independent set of a 3-regular graph
• The maximum genus of a 3-regular simplicial graph
• Induced graphs of uniform spanning forests
• Dominating and large induced trees in regular graphs
• Lower Bounds For Induced Forests in Cubic Graphs
• The k-conversion number of regular graphs
• Induced forests in bipartite planar 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
• Induced path factors of regular graphs
• Cycle-compelling colorings of graphs
• Upper-embeddability and the decycling number of connected 4-regular graphs
• On the maximum induced forests of a connected cubic graph without triangles

This page was built for publication: Induced forests in cubic graphs

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