A tournament T is an orientation of a complete graph, and a feedback vertex set of T is a subset of vertices intersecting every directed cycle of T. We prove that every tournament on n vertices has at most 1:6740n minimal feedback vertex sets and some tournaments have 1:5448n minimal feedback vertex sets. This improves a result by Moon (1971) who showed upper and lower bounds of 1:7170n and 1:4757n on the maximum number of minimal feedback vertex sets in tournaments.

Original language | English |
---|

Publisher | s.n. |
---|

Number of pages | 18 |
---|

Publication status | Published - 2009 |
---|

Name | arXiv.org [cs.DM] |
---|

Volume | 0905.0567 |
---|