zbMATH — the first resource for mathematics

Trees in tournaments. (English) Zbl 1048.05040
Summary: In 1971, Sumner conjectured that any tournament of order $$2(n-1)$$ contains any oriented tree of order $$n$$. Since then several bounds have been established that get closer and closer to the suggested bound $$2(n-1)$$. In this paper we prove that any tournament of order $$3(n-1)$$ contains any oriented tree of order $$n$$.

MSC:
 05C20 Directed graphs (digraphs), tournaments 05C05 Trees
Keywords:
tournament; oriented tree
Full Text:
References:
 [1] S.A. Burr, Subtrees of directed graphs and hypergraphs, in: Proceedings of the 11th Southeastern Conference on Combinatorics, Graph theory and Computing, I, Vol. 28, Florida Atlantic University, Boca Raton, FL, 1980, pp. 227-239. · Zbl 0453.05022 [2] Häggkvist, R.; Thomason, A.G., Trees in tournaments, Combinatorica, 11, 123-130, (1991) · Zbl 0736.05041 [3] Havet, F., Trees in tournament, J. discrete math., 243, 1-3, 121-134, (2002) · Zbl 0995.05037 [4] Havet, F.; Thomassé, S., Median orders of tournamentsa tool for the second neighborhood problem and Sumner’s conjecture, J. graph theory, 35, 244-256, (2000) · Zbl 0969.05029 [5] Rédei, L., Ein kombinatorischer satz, Acta litt. Szeged, 7, 39-43, (1934) · Zbl 0009.14606 [6] Reid, K.B.; Wormald, N.C., Stud. sci. math. hungaria, 18, 377-387, (1983) [7] A. El Sahili, Paths with two blocks in k-chromatic graphs, Discrete Math., to appear. · Zbl 1050.05072 [8] N.C. Wormald, Subtrees of large tournaments, in: Combinatorial Mathematics, X (Adelaide, 1982). Lecture Notes in Mathematics, Vol. 1036, Springer, Berlin, 1983, pp. 417-419.
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.