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

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