##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 253.05124

**Autor: ** Brown, William G.; Erdös, Paul; Simonovits, Miklos

**Title: ** Extremal graph problems for directed graphs. (In English)

**Source: ** J. Comb. Theory, Ser. B 15, 77-93 (1973).

**Review: ** We consider directed graphs without loops and multiple edges, where the exclusion of multiple edges means that two vertices cannot be joined by two edges of the same orientation. Let L_{1}, ... ,L_{q} be given digraphs. What is the maximum number of edges a digraph can have if it does not contain any L_{i} as a subgraph and has given number of vertices? We shall prove the existence of a sequence of asymptotical extremal graphs having fairly simple structure. More exactly: There exists a matrix A = (a_{i,j})_{i,j \leq r} and a sequence **{**S^{n} **}** of graphs such that (i) the vertices of S^{n} can be divided into classes C_{1}, ... ,C_{r} so that, if i \ne j, each vertex of C_{i} is joined to each vertex of C_{j} by an edge oriented from C_{i} to C_{j} if and only if a_{i,j} = 2; the vertices of C_{i} are independent if a_{i,i} = 0; and otherwise a_{i,i} = 1 and the digraph determined by C_{i} is a complete acyclic digraph; (ii) S^{n} contains no L_{i} but any graph having [\epsilon n^{2}] more edges than S^{n} must contain at least one L_{i}. (Here the word graph is an ``abbreviation'' for ``directed graph or digraph''.)

**Classif.: ** * 05C20 Directed graphs (digraphs)

05C35 Extremal problems (graph theory)

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag