Skip to main content

Research Repository

Advanced Search

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

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

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


Authors

F.R. Madelaine



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
Electronic ISSN 2578-9252
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.
Public URL https://durham-repository.worktribe.com/output/1553374
Publisher URL http://www.dur.ac.uk/i.a.stewart/Papers/FVSGridsAndButterflies.pdf

Files






You might also like



Downloadable Citations