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

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

doi:10.1016/j.disc.2007.08.007

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

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

Authors

F.R. Madelaine

Professor Iain Stewart i.a.stewart@durham.ac.uk
Professor

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