Tournaments with maximal decomposability

Abstract

Given a tournament $T$, a module of $T$ is a subset $M$ of $V(T)$ such that for $x,y\in M$ and $v\in V(T)\setminus M$, $(x,v)\in A(T)$ if and only if $(y,v)\in A(T)$. The trivial modules of $T$ are $\varnothing$, $\{u\}$ $(u\in V(T))$ and $V(T)$. The tournament $T$ is indecomposable if all its modules are trivial; otherwise it is decomposable. The decomposability index of $T$, denoted by $\delta (T)$, is the smallest number of arcs of $T$ that must be reversed to make $T$ indecomposable. In a previous paper, we proved that for $n\ge 5$, we have $\delta (n)=\lceil \frac{n+1}{4}\rceil$, where $\delta (n)$ is the maximum of $\delta (T)$ over the tournaments $T$ with $n$ vertices. In this paper, we characterize the tournaments $T$ with $\delta$-maximal decomposability, i.e., such that $\delta (T)=\delta (|T|)$.

14 pages with 2 figures. arXiv admin note: text overlap with arXiv:2003.06503