Paper Info
Title
Complete classification of tournaments having a disjoint union of directed paths as a minimum feedback arc set
Abstract
A feedback arc set of a digraph is a set of arcs whose reversal makes the resulting digraph acyclic. Given a tournament with a disjoint union of directed paths as a feedback arc set, we present necessary and sufficient conditions for this feedback arc set to have minimum size. We will present a construction for tournaments where the difference between the size of a minimum feedback arc set and the size of the largest collection of arc disjoint cycles can be made arbitrarily large. We will also make a connection to a problem found in [Barthélemy et al., [2]. The reversing number of a digraph was defined to be $r(D)\, = |V(T)|-|V(D)|$ where T is a smallest tournament having the arc set of D as a minimum feedback arc set. As a consequence of our classification of all tournaments having a disjoint union of directed paths as a minimum feedback arc set, we will obtain a new result involving the reversing number. We obtain precise reversing numbers for all digraphs consisting of a disjoint union of directed paths. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 28–47, 2004
Year
DOI
Venue
2004
10.1002/jgt.v45:1
Journal of Graph Theory
Keywords
Field
DocType
feedback arc sets,linear ordering problem,tournaments
Graph theory,Discrete mathematics,Tournament,Combinatorics,Arc (geometry),Disjoint sets,Disjoint union,Feedback arc set,Arbitrarily large,Digraph,Mathematics
Journal
Volume
Issue
ISSN
45
1
0364-9024
Citations 
PageRank 
References 
3
0.55
2
Authors
2
Name
Order
Citations
PageRank
Garth Isaak117224.01
Darren A. Narayan2197.72