Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 267.05104
Autor: Erdös, Paul; Fried, E.; Hajnal, András; Milner, E.C.
Title: Some remarks on simple tournaments. (In English)
Source: Algebra universalis 2, 238-245 (1972).
Review: A tournament consists of a set T of points on which is defined a complete, anti-symmetric, irreflexive binary relation \rho. A non-empty proper subset X of T is convex if for each y in T-X either x \rho y for all x in X or y \rho x for all x in X. A tournament is simple if it has no convex subsets with more than one point. The authors prove that almost all finite tournaments are simple and that for any tournament T with |T| \ne 2 there exists a simple tournament R such that T \subset R and |R-T| = 2. (Criteria for a tournament to have a simple one-point extension have been given by the reviewer [Discrete Math. 2, 389-395 (1972; Zbl 236.05108)] when T is finite and by P. Erdös, A. Hajnal and E. C. Milner [Mathematika, London 19, 57-62 (1972; Zbl 242.05113)] in the general case.)
Reviewer: J.W.Moon
Classif.: * 05C20 Directed graphs (digraphs)
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag