zbMATH — the first resource for mathematics

Largest digraphs contained in all n-tournaments. (English) Zbl 0532.05032
Let f(n) denote the largest integer such that there exists a directed graph D with n vertices and f(n) edges that is contained in every tournament with n vertices. The authors show, among other things, that \(c_ 1n\leq n \log_ 2n-f(n)\leq c_ 2n \log \log n\) for suitable constants \(c_ 1\) and \(c_ 2\).
Reviewer: J.W.Moon

05C20 Directed graphs (digraphs), tournaments
05C35 Extremal problems in graph theory
Full Text: DOI
[1] B. Alspach andM. Rosenfeld, Realization of certain generalized paths in tournaments,Discr. Math. 34 199–202. · Zbl 0453.05031
[2] P. Erdos andL. Moser, On the representation of directed graphs as unions of orderings,Publ. Math. Inst. Hungar. Acad. Sci. 9 (1964), 125–132. · Zbl 0136.44901
[3] R. Forcade, Parity of paths and circuits in tournaments,Discr. Math. 6 (1973), 115–118. · Zbl 0268.05108 · doi:10.1016/0012-365X(73)90041-1
[4] B. Grünbaum, Antidirected Hamiltonian Paths in tournaments,J. Combinatorial Theory (B) 11 (1971), 249–257. · Zbl 0219.05063 · doi:10.1016/0095-8956(71)90035-9
[5] H. G. Landau, On dominance relations and the structure of animal societies, III; the condition for a score structure,Bull. Math. Biophys. 15 (1955), 143–148. · doi:10.1007/BF02476378
[6] J. W. Moon,Topics on tournaments, Holt, Rinehart and Winston, New York, 1968. · Zbl 0191.22701
[7] L. Rédei, Ein Kombinatorischer Satz,Acta Sci. Math. (Szeged) 7 (1934), 39–43.
[8] M. Rosenfeld, Antidirected Hamiltonian Circuits in tournaments,J. Combinatorial Theory (B) 16 (1974), 234–242. · Zbl 0279.05111 · doi:10.1016/0095-8956(74)90069-0
[9] M. Saks andV. T. Sóss, On unavoidable subgraphs of tournaments, to appear. · Zbl 0566.05032
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.