×

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
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Häggkvist, R; Thomason, A.G, Trees in tournaments, Combinatorica, 11, 123-130, (1991) · Zbl 0736.05041
[2] Havet, F, Trees in tournaments, Discrete math., 243, 121-134, (2002) · Zbl 0995.05037
[3] Havet, F, On unavoidability of trees with k leaves, Graphs combin., 19, 101-110, (2003) · Zbl 1022.05014
[4] 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
[5] 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
[6] Lu, X; Wang, D; Wong, C.K, On avoidable and unavoidable claws, Discrete math., 184, 259-265, (1998) · Zbl 0958.05059
[7] Reid, K.B; Wormald, N.C, Embedding oriented n-trees in tournaments, Studia sci. math. hungar., 18, 377-387, (1983) · Zbl 0489.05026
[8] 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.