Indecomposable Tournaments and Their Indecomposable Subtournaments on $5$ and $7$ Vertices

Abstract

Given a tournament $T=(V,A)$, a subset $X$ of $V$ is an interval of $T$ provided that for every $a,b\in X$ and $x\in V–X$, $(a,x)\in A$ if and only if $(b,x)\in A$. For example, $\mathrm{\varnothing }$, $\{x\}$ ($x\in V$), and $V$ are intervals of $T$, called trivial intervals. A tournament, all the intervals of which are trivial, is indecomposable; otherwise, it is decomposable. A critical tournament is an indecomposable tournament $T$ of cardinality $\ge 5$ such that for any vertex $x$ of $T$, the tournament $T–x$ is decomposable. The critical tournaments are of odd cardinality and for all $n\ge 2$ there are exactly three critical tournaments on $2n+1$ vertices denoted by $T_{2n+1}$, $U_{2n+1}$, and $W_{2n+1}$. The tournaments $T_5$, $U_5$, and $W_5$ are the unique indecomposable tournaments on 5 vertices. We say that a tournament $T$ embeds into a tournament $T^{\prime }$ when $T$ is isomorphic to a subtournament of $T^{\prime }$. A diamond is a tournament on 4 vertices admitting only one interval of cardinality 3. We prove the following theorem: if a diamond and $T_5$ embed into an indecomposable tournament $T$, then $W_5$ and $U_5$ embed into $T^{\prime }$. To conclude, we prove the following: given an indecomposable tournament $T$ with $|V(T)|\ge 7$, $T$ is critical if and only if only one of the tournaments $T_7$, $U_7$, or $W_7$ embeds into $T$.