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, c1,c2, ... denote suitable positive constants.) Theorem. c1n log n/ log log n < f(n,n) < c2n log n. The graph constructed in order to establish the upper bound on f(n,n) has c3n vertices. In this case, the upper bound is essentially best possible since it is shown that for c4 sufficiently large, if a graph on c4n vertices has property P(n,n) then it must have at least c5n log n edges.
Reviewer: L.Lesniak
Classif.: * 05C35 Extremal problems (graph theory)
05C20 Directed graphs (digraphs)
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag