Premium
Complete classification of tournaments having a disjoint union of directed paths as a minimum feedback arc set
Author(s) -
Isaak Garth,
Narayan Darren A.
Publication year - 2004
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10155
Subject(s) - digraph , tournament , disjoint sets , feedback arc set , mathematics , combinatorics , arc (geometry) , directed graph , set (abstract data type) , reversing , disjoint union (topology) , path (computing) , discrete mathematics , connection (principal bundle) , graph , computer science , geometry , materials science , voltage graph , line graph , composite material , programming language
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