Improved upper and lower bounds on the feedback vertex numbers of grids and butterflies

DOI10.1016/j.disc.2007.08.007zbMath1154.05055OpenAlexW1985300267MaRDI QIDQ941343

Florent R. Madelaine, Iain A. Stewart

Publication date: 4 September 2008

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

Full work available at URL: https://doi.org/10.1016/j.disc.2007.08.007

zbMATH Keywords

gridsfeedback vertex setsbutterflies

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

Circular convex bipartite graphs: feedback vertex sets ⋮ The decycling number of $P_{m} \square P_{n}^{\ast}$ ⋮ Feedback vertex sets on restricted bipartite graphs ⋮ New bounds on the decycling number of generalized de Bruijn digraphs ⋮ On the decycling number of generalized Kautz digraphs ⋮ Two Hardness Results on Feedback Vertex Sets ⋮ Feedback arc number and feedback vertex number of Cartesian product of directed cycles ⋮ Circular Convex Bipartite Graphs: Feedback Vertex Set ⋮ Feedback vertex number of Sierpiński-type graphs

Cites Work

• Almost exact minimum feedback vertex set in meshes and butterflies
• New bounds on the size of the minimum feedback vertex set in meshes and butterflies.
• New upper bounds on feedback vertex numbers in butterflies

This page was built for publication: Improved upper and lower bounds on the feedback vertex numbers of grids and butterflies