##
**Zentralblatt MATH**

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

**Zbl.No: ** 607.05040

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

**Title: ** Algorithmic solution of extremal digraph problems. (In English)

**Source: ** Trans. Am. Math. Soc. 292, 421-449 (1985).

**Review: ** For a given family *L* of digraphs, the maximum number ex(n,*L*) of arcs a digraph on n vertices containing no member of *L* can possesses and the set Ex(n,*L*) of digraphs which attain this maximum are studied. In particular, the asymptotic behaviour of ex(n,*L*)/n^{2} is discussed in detail.

For a square matrix A, a sequence A(n) of digraphs, called matrix digraphs, are defined which are of, in some sense, simple structure. An algorithm is given to determine all matrices A such that each A(n) contains no member of *L*, and has ex(n,*L*)+o(n^{2}) arcs as n ––> oo.

**Reviewer: ** Z.Ma

**Classif.: ** * 05C35 Extremal problems (graph theory)

05C20 Directed graphs (digraphs)

**Keywords: ** digraphs

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag