On feedback vertex sets in tournaments

S. Gaspers, M. Mnich

Onderzoeksoutput: Boek/rapportRapportAcademic

Samenvatting

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.
Originele taal-2Engels
Uitgeverijs.n.
Aantal pagina's18
StatusGepubliceerd - 2009

Publicatie series

NaamarXiv.org [cs.DM]
Volume0905.0567

Vingerafdruk Duik in de onderzoeksthema's van 'On feedback vertex sets in tournaments'. Samen vormen ze een unieke vingerafdruk.

Citeer dit