Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

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

Madelaine, F. R. and Stewart, I. A. (2008) 'Improved upper and lower bounds on the feedback vertex numbers of grids and butterflies.', Discrete mathematics., 308 (18). pp. 4144-4164.

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.

Item Type:Article
Keywords:Feedback vertex set, Grids, Butterflies.
Full text:(AM) Accepted Manuscript
Download PDF
(340Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1016/j.disc.2007.08.007
Date accepted:No date available
Date deposited:29 June 2009
Date of first online publication:September 2008
Date first made open access:No date available

Save or Share this output

Export:
Export
Look up in GoogleScholar