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