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\leq \left \vert M\right \vert \leq n-1$ and for every $x\in V\setminus M$, either $M\rightarrow x$ or $x\rightarrow M$. The simplicity index of an $n$-tournament $T$ is the minimum number $s(T)$ of arcs whose reversal yields a nonsimple tournament. Müller and Pelant (1974) proved that $s(T)\leq(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\pmod{4}$, $s(T)<(n-1)/2$ for $n\not\equiv3\pmod{4}$. In this paper, we study the class of $n$-tournaments with maximal simplicity index for $n\not\equiv3\pmod{4}$.