On the reversing number of powers of directed hamiltonian paths

Abstract

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_n^k. We present new reversing numbers for the square and cube of a directed Hamiltonian path. In fact, we precisely determine r (P_n^k) for all k ≤ 7, and investigate the general case for arbitrarily large k.