Accession Number : ADA017370

Title :   On Sparse Graphs with Dense Long Paths.

Descriptive Note : Technical rept.,

Corporate Author : STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

Personal Author(s) : Erdos,P. ; Graham,R. L. ; Szemeredi,E.

Report Date : SEP 1975

Pagination or Media Count : 17

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.

Descriptors :   *Boolean algebra, Set theory, Theorems

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE