Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  242.05113
Autor:  Erdös, Paul; Hajnal, András; Milner, E.C.
Title:  Simple one-point extensions of tournaments. (In English)
Source:  Mathematika, Lond. 19, 57-62 (1972).
Review:  A tournament T consists of a set of points on which is defined a complete, anti-symmetric, irreflexive binary relation \rho. A tournament T is simple if it is impossible to define a non-trivial equivalence relation on the points of T with the property that if x \rho y then x' \rho y' for all pairs of points x' and y' that are equivlent to x and y, respectively. If T is a subtournament of T' and |T' - T| = k then T' is a k-point extension of T. The authors prove that s (finite or infinite) tournament T has a simple 1-point extension except when T is a 3-cycle of a non-trivial finite transitive tournament with an odd number of points.
Reviewer:  J.W.Moon
Classif.:  * 05C20 Directed graphs (digraphs)

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page