##
**Zentralblatt MATH**

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

**Zbl.No: ** 328.05123

**Autor: ** Erdös, Paul; Graham, Ronald L.; Szemeredi, E.

**Title: ** On sparse graphs with dense long paths. (In English)

**Source: ** Comput. Math. Appl. 1, 365-369 (1975).

**Review: ** An acyclic directed graph G is said to have property P(m,n) if for any set X of m vertices of G, there is a directed path of length n in G which does not intersect X. Let f(m,n) denote the minimum number of edges a graph with property P(m,n) can have. (Hereafter, c_{1},c_{2}, ... denote suitable positive constants.) Theorem. c_{1}n log n/ log log n < f(n,n) < c_{2}n log n. The graph constructed in order to establish the upper bound on f(n,n) has c_{3}n vertices. In this case, the upper bound is essentially best possible since it is shown that for c_{4} sufficiently large, if a graph on c_{4}n vertices has property P(n,n) then it must have at least c_{5}n log n edges.

**Reviewer: ** L.Lesniak

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

05C20 Directed graphs (digraphs)

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag