Abstract
Letf(n) (resp.g(n)) be the largestm such that there is a digraph (resp. a spanning weakly connected digraph) onn-vertices andm edges which is a subgraph of every tournament onn-vertices. We prove that
Similar content being viewed by others
References
B. Alspach andM. Rosenfeld, Realization of certain generalized paths in tournaments,Discr. Math. 34 199–202.
P. Erdős andL. Moser, On the representation of directed graphs as unions of orderings,Publ. Math. Inst. Hungar. Acad. Sci. 9 (1964), 125–132.
R. Forcade, Parity of paths and circuits in tournaments,Discr. Math. 6 (1973), 115–118.
B. Grünbaum, Antidirected Hamiltonian Paths in tournaments,J. Combinatorial Theory (B) 11 (1971), 249–257.
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.
J. W. Moon,Topics on tournaments, Holt, Rinehart and Winston, New York, 1968.
L. Rédei, Ein Kombinatorischer Satz,Acta Sci. Math. (Szeged) 7 (1934), 39–43.
M. Rosenfeld, Antidirected Hamiltonian Circuits in tournaments,J. Combinatorial Theory (B) 16 (1974), 234–242.
M. Saks andV. T. Sóss, On unavoidable subgraphs of tournaments, to appear.
Author information
Authors and Affiliations
Additional information
Supported by the Chaim Weizman Postdoctoral Fellowship.
Supported in part by NSF under grant No. MCS-8102448.