The simplicity index of tournaments

Abstract

An $n$-tournament $T$ with vertex set $V$ is simple if there is no subset $M$ of $V$ such that $2\le \left|M\right|\le n-1$ and for every $x\in V\setminus M$, either $M\to x$ or $x\to M$. The simplicity index of an $n$-tournament $T$ is the minimum number $s(T)$ of arcs whose reversal yields a non-simple tournament. Müller and Pelant (1974) proved that $s(T)\le \frac{n-1}{2}$, and that equality holds if and only if $T$ is doubly regular. As doubly regular tournaments exist only if $n\equiv 3(\mathrm{mod}4)$, $s(T)<\frac{n-1}{2}$ for $n\not\equiv 3(\mathrm{mod}4)$. In this paper, we study the class of $n$-tournaments with maximal simplicity index for $n\not\equiv 3(\mathrm{mod}4)$.