Solution of a Conjecture of Vandell on Decycling Bipartite Tournaments by Deleting Arcs

Abstract

The decycling index of a digraph is the minimum number of arcs whose removal yields an acyclic digraph. The maximum arc decycling number ${\overline{\mathrm{\nabla }}}^{\prime }(m,n)$ is the maximum decycling index among all $m\times n$ bipartite tournaments. Recently, R.C. Vandell determined the numbers ${\overline{\mathrm{\nabla }}}^{\prime }(2,n)$, ${\overline{\mathrm{\nabla }}}^{\prime }(3,n)$, and ${\overline{\mathrm{\nabla }}}^{\prime }(4,n)$ for all positive integers $n$, as well as ${\overline{\mathrm{\nabla }}}^{\prime }(5,5)$. In this work, we use a computer program to obtain ${\overline{\mathrm{\nabla }}}^{\prime }(5,6)$, ${\overline{\mathrm{\nabla }}}^{\prime }(6,6)$, and ${\overline{\mathrm{\nabla }}}^{\prime }(5,7)$, as well as some results on ${\overline{\mathrm{\nabla }}}^{\prime }(6,7)$ and ${\overline{\mathrm{\nabla }}}^{\prime }(5,8)$. In particular, ${\overline{\mathrm{\nabla }}}^{\prime }(6,6)=10$, and this confirms a conjecture of Vandell.