On feedback vertex sets in tournaments

S. Gaspers, M. Mnich

Research output: Book/ReportReportAcademic


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 languageEnglish
Number of pages18
Publication statusPublished - 2009

Publication series

NamearXiv.org [cs.DM]


Dive into the research topics of 'On feedback vertex sets in tournaments'. Together they form a unique fingerprint.

Cite this