zbMATH — the first resource for mathematics

On unavoidable subgraphs of tournaments. (English) Zbl 0566.05032
Finite and infinite sets, 6th Hung. Combin. Colloq., Eger/Hung. 1981, Vol. II, Colloq. Math. Soc. János Bolyai 37, No. 2, 663-674 (1984).
[For the entire collection see Zbl 0559.00001.]
A digraph is called n-unavoidable iff it is contained in every tournament of cardinality n. An old result of L. Rédei [Acta Litt. Sci. Szeged 7, 39-43 (1934; Zbl 0009.14606)] says that a dipath of length n is n- unavoidable because each tournament contains a Hamilton path. Also a transitive tournament of \(\lceil \log_ 2n\rceil +1\) vertices is n- unavoidable as P. Erdős and J. W. Moon [Can. Math. Bull. 8, 269-271 (1965; Zbl 0137.433)] have shown.
In this paper the authors largely restricted themselves to the problem of identifying spanning rooted directed trees which are n-unavoidable and showed that subclasses of claws, which are rooted trees in which every branch is a dipath, are n-unavoidable. In another section they proved that there are spanning rooted trees of depth 3, which are n-unavoidable. This result is nearly best possible, because the smallest depth, which can be expected, is 2.
Reviewer: M.Hager

05C20 Directed graphs (digraphs), tournaments
05C05 Trees
05C35 Extremal problems in graph theory