Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 263.05108
Autor: Entringer, Roger C.; Erdös, Paul; Harner, C.C.
Title: Some extremal properties concerning transitivity in graphs. (In English)
Source: Period. Math. Hung. 3, 275-279 (1973).
Review: A directed graph D is transitive iff arc ac is in D whenever arcs ab and bc are in D. We show that for all tournaments Tn on n points, with 0 (2\binom{n{2}} ) exceptions, the largest transitive subgraph of Tn contains fewer than 1/4 \binom{n}{2}+cn3/2 arcs for a suitable constant c. Results concerning the size of bipartite subgraphs of tournaments and transitive graphs are also obtained.
Classif.: * 05C20 Directed graphs (digraphs)
05C35 Extremal problems (graph theory)
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag