SUBTOURNAMENTS ISOMORPHIC TO W5OF AN INDECOMPOSABLE TOURNAMENT
Houmem Belkhechine, Imed Boudabbous, Kaouthar Hzami · Journal of the Korean Mathematical Society · 2012
We consider a tournament T = (V,A). For each subset X of V is associated the subtournament T(X) = (X, $A{\cap}(X{\times}X)$ ) of T induced by X. We say that a tournament T' embeds into a tournament T when T' is isomorphic to a subtournament of T. Otherwise, we say that T omits T'. A subset X of V is a clan of T provided that for a, $b{\in}X$ and $x{\in}V{\backslash}X$ , $(a,x){\in}A$ if and only if $(b,x){\in}A$ . For example, ${\emptyset}$ , $\{x\}(x{\in}V)$ and V are clans of T, called trivial clans. A tournament is indecomposable if all its clans are trivial. In 2003, B. J. Latka characterized the class ${\tau}$ of indecomposable tournaments omitting a certain tournament $W_5$ on 5 vertices. In the case of an indecomposable tournament T, we will study the set $W_5$ (T) of vertices $x{\in}V$ for which there exists a subset X of V such that $x{\in}X$ and T(X) is isomorphic to $W_5$ . We prove the following: for any indecomposable tournament T, if $T{ otin}{\tau}$ , then ${\mid}W_5(T){\mid}{\geq}{\mid}V{\mid}$ -2 and ${\mid}W_5(T){\mid}{\geq}{\mid}V{\mid}$ -1 if ${\mid}V{\mid}$ is even. By giving examples, we also verify that this statement is optimal.