On unavoidable subdigraphs of tournaments


Vojislav Petrović




A digraph $D$ is $n$-unavoidable if each tournament on $n$ vertices contains a subdiagraph isomorphic to $D$. It is proved a that the diagraph $H(n,i)$ defined as a simple $n$-path $v_1\to v_2\to\dots\to v_n$ with an aditional are $v_1v_i(3\leq i\leq n)$, is $n$-unavoidable for each $n(n\geq 4)$ and $i=4$. So are $H(n,3)$ and $H(n,n-1)$ for $n\geq 4$, excluding two particular cases.