# zbMATH — the first resource for mathematics

Trees with three leaves are ($$n+1$$)-unavoidable. (English) Zbl 1043.05057
Summary: We prove that every tree of order $$n \geqslant 5$$ with three leaves is ($$n+1$$)-unavoidable. More precisely, we prove that every tree $$A$$ with three leaves of order $$n$$ is contained in every tournament $$T$$ of order $$n+1$$ except if $$(T;A)$$ is $$(R_5;S_3^+)$$ or its dual, where $$R_5$$ is the regular tournament on five vertices and $$S_3^+$$ is the outstar of degree three, i.e. the tree consisting of a root dominating three leaves. We then deduce that Sumner’s conjecture is true for trees with four leaves, i.e. every tree of order $$n$$ with four leaves is $$(2n-2)$$-unavoidable.

##### MSC:
 05C20 Directed graphs (digraphs), tournaments 05C05 Trees
##### Keywords:
Tournament; Unavoidable; Tree
Full Text:
##### References:
  Häggkvist, R; Thomason, A.G, Trees in tournaments, Combinatorica, 11, 123-130, (1991) · Zbl 0736.05041  Havet, F, Trees in tournaments, Discrete math., 243, 121-134, (2002) · Zbl 0995.05037  Havet, F, On unavoidability of trees with k leaves, Graphs combin., 19, 101-110, (2003) · Zbl 1022.05014  Havet, F; Thomassé, S, Oriented Hamiltonian paths in tournamentsa proof of Rosenfeld’s conjecture, J. combin. theory ser. B, 78, 243-273, (2000) · Zbl 1026.05053  Havet, F; Thomassé, S, Median ordera tool for the second neighborhood problem and Sumner’s conjecture, J. graph theory, 35, 244-256, (2000) · Zbl 0969.05029  Lu, X; Wang, D; Wong, C.K, On avoidable and unavoidable claws, Discrete math., 184, 259-265, (1998) · Zbl 0958.05059  Reid, K.B; Wormald, N.C, Embedding oriented n-trees in tournaments, Studia sci. math. hungar., 18, 377-387, (1983) · Zbl 0489.05026  Thomason, A.G, Paths and cycles in tournaments, Trans. amer. math. soc., 296, 167-180, (1986) · Zbl 0599.05026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.