The reversing number of a digraph
Given an acyclic digraph \(D\), the authors investigate the problem of determining the size of the smallest tournament \(T\) which has the arc set of \(D\) as a minimum reversing set. A minimum reversing set of a digraph is a smallest set of arcs which, when reversed, make a digraph acyclic. It is shown that there exists a smallest sized \(T\) which has an arc set of \(D\) as a minimum reversing set. Bounds are determined and exact values of the reversing sets for several special classes of acyclic digraphs are established.
scientific article; zbMATH DE number 777814
scientific article