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, $\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' when T is isomorphic to a subtournament of T'. 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. To conclude, we prove the following: given an indecomposable tournament T, with $\mid V(T)\mid \ge 7$, T is critical if and only if the indecomposable subtournaments on 7 vertices of T are isomorphic to one and only one of the tournaments $T_7$, $U_7$ and $W_7$.

12 pages, to appear in Ars Combinatoria

Cited by in corpus (1)

• (-k)-critical trees and k-minimal trees