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 |
|---|