##
**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 T_{n} on n points, with 0 **(**2^{\binom{n}{2}} **)** exceptions, the largest transitive subgraph of T_{n} contains fewer than ^{1}/_{4} \binom{n}{2}+cn^{3/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