A minimum feedback arc set of a digraph is a smallest sized set of arcs that when reversed makes the resulting digraph acyclic. Given an acyclic digraph D, we seek a smallest sized tournament T that has D as a minimum feedback arc set. The reversing number of a digraph is defined to be r(D) = V(T) - |V(D)|. We use methods from integer programming and combinatorial design theory to obtain new results for reversing numbers where D is a power of a directed Hamiltonian path, P￡- We present new reversing numbers for the square and cube of a directed Hamiltonian path. In fact, we precisely determine r (P%) for all k < 7, and investigate the general case for arbitrarily large k.
展开▼
