Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 137.43301
Autor: Erdös, Pál; Moon, J.W.
Title: On sets of consistent arcs in a tournament (In English)
Source: Can. Math. Bull. 8, 269-271 (1965).
Review: Ein Turnier Tn ist ein gerichteter Graph mit n Ecken e1,...,en in dem für \nu \ne \mu genau eine der Kanten \overrightarrow {e\nu e\mu} oder \overrightarrow {e\mu e\nu} existiert. Eine Menge von Kanten in Tn heißt azyklisch, wenn der durch sie bestimmte Teilgraph keine orientierten Kreise enthält. f(n) bezeichne das maximale k, so daß jedes Tn eine k-elementige azykliche Kantenmenge enthält. Die Verff. zeigen: [ n/2 ] [{n+1 \over 2} ] \leq f(n) < 1/2 {n \choose 2}+( 1/2 +o(1)) (n3 log n) ½ und erwähnen eine Eigenschaft der entsprechenden (allgemeineren) Funktion f(n,m) für Graphen G(n,m) mit n Ecken und m Kanten.
Reviewer: H.A.Jung
Classif.: * 05C20 Directed graphs (digraphs)
05C35 Extremal problems (graph theory)
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag