zbMATH — the first resource for mathematics

Median orders of tournaments: A tool for the second neighborhood problem and Sumner’s conjecture. (English) Zbl 0969.05029
A median order of a tournament \(T=(V,E)\) is an acyclic tournament \(L=(V,A)\) which is a total order of the vertices of \(T\) and which maximizes the number of arcs belonging to \(E\cap A.\) The authors apply median orders of tournaments as a tool to prove two results: (1) a theorem of D. C. Fisher [J. Graph Theory 23, No. 1, 43-48 (1996; Zbl 0857.05042)]: every tournament contains a vertex whose second outneighborhood is as large as its first outneighborhood; and (2) every tournament of order \(\frac{7n-5}{2}\) contains every oriented tree of order \(n\) (a particular case of Sumner’s conjecture; see N. C. Wormald [Lect. Notes Math. 1036, 417-419 (1983; Zbl 0521.05032)]).

05C20 Directed graphs (digraphs), tournaments
Full Text: DOI
[1] Charon, Discrete Math 165/166 pp 139– (1997) · Zbl 0878.68090 · doi:10.1016/S0012-365X(96)00166-5
[2] Dean, Congr Numer 109 pp 73– (1995)
[3] Fisher, J Graph Theory 23 pp 43– (1996) · Zbl 0857.05042 · doi:10.1002/(SICI)1097-0118(199609)23:1<43::AID-JGT4>3.0.CO;2-K
[4] Fisher, J Graph Theory 19 pp 217– (1995) · Zbl 0823.90142 · doi:10.1002/jgt.3190190208
[5] Häggkvist, Combinatorica 11 pp 123– (1991) · Zbl 0736.05041 · doi:10.1007/BF01206356
[6] Havet, Discrete Math
[7] Reid, Studia Sci Math Hungar 18 pp 377– (1983)
[8] Wormald, Lecture Notes in Math 1036 pp 417– (1983) · doi:10.1007/BFb0071535
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.