On Sparse Graphs with Dense Long Paths.
Abstract
The following problem was raised by H.-J. Stoss in connection with certain questions related to the complexity of Boolean functions. An acyclic directed graph G is said to have property p (m,n) if for any set of 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1975
- Accession Number
- ADA017370
Entities
People
- E. Szemeredi
- P. Erdos
- R. L. Graham
Organizations
- Stanford University