A new bound on the feedback vertex sets in cubic graphs

DOI10.1016/0012-365X(94)00268-NzbMath0922.05033OpenAlexW2009278424MaRDI QIDQ1910543

Cheng Zhao, Ji Ping Liu

Publication date: 24 March 1996

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(94)00268-n

zbMATH Keywords

boundcubic graphsfeedback set

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)

Related Items (12)

Unnamed Item ⋮ A lower bound on the order of the largest induced forest in planar graphs with high girth ⋮ Boundary classes for graph problems involving non-local properties ⋮ Splitting plane graphs to outerplanarity ⋮ Induced forests in some distance-regular graphs ⋮ Constraint bipartite vertex cover: simpler exact algorithms and implementations ⋮ New formulae for the bipartite vertex frustration and decycling number of graphs ⋮ A lower bound on the $k$-conversion number of graphs of maximum degree $k+1$ ⋮ The k-conversion number of regular graphs ⋮ Feedback vertex sets in cubic multigraphs ⋮ Maximum genus, girth and connectivity ⋮ Maximum genus and girth of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• On the maximum induced forests of a connected cubic graph without triangles
• Lower Bounds For Induced Forests in Cubic Graphs
• On feedback vertex sets and nonseparating independent sets in cubic graphs
• The Rectilinear Steiner Tree Problem is $NP$-Complete

This page was built for publication: A new bound on the feedback vertex sets in cubic graphs