Tournaments with Feedback Path Powers

Abstract

A minimum feedback arc set of a digraph is a smallest sized set of arcs whose reversal makes the resulting digraph acyclic. Given an acyclic digraph $D$, we seek a smallest sized tournament $T$ having $A(D)$ as a minimum feedback arc set. The reversing number of a digraph $D$ equals $|V(T)|–|V(D)|$. We investigate the reversing number of the $k$th power of directed Hamiltonian path $P_n^k$, when $k$ is fixed and $n$ tends to infinity. We show that even for small values of $k$, where $|A(P_n^k)|$ is much closer to $|A(P_n)|$ than $|A(T_n)|$, the opposite relationship holds for the reversing number.