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

Madelaine, F.R.; Stewart, I.A.

Abstract

We improve upon the best known upper and lower bounds on the sizes of minimal feedback vertex sets in butterflies. Also, we construct new feedback vertex sets in grids so that for a large number of pairs $(n,m)$, the size of our feedback vertex set in the grid $M_{n,m}$ matches the best known lower bound, and for all other pairs it differs from this lower bound by at most 2.

Citation

Madelaine, F., & Stewart, I. (2008). Improved upper and lower bounds on the feedback vertex numbers of grids and butterflies. Discrete Mathematics, 308(18), 4144-4164. https://doi.org/10.1016/j.disc.2007.08.007

• Journal Article Type: Article
• Publication Date: Sep 1, 2008
• Deposit Date: Jun 29, 2009
• Publicly Available Date: Jun 29, 2009
• Journal: Discrete mathematics.
• Print ISSN: 0012-365X
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 308
• Issue: 18
• Pages: 4144-4164
• DOI: https://doi.org/10.1016/j.disc.2007.08.007
• Keywords: Feedback vertex set, Grids, Butterflies.
• Publisher URL: http://www.dur.ac.uk/i.a.stewart/Papers/FVSGridsAndButterflies.pdf