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):

Report Date:

1975-09-01

Pagination or Media Count:

17.0

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 fm,n denote the minimum number of edges a graph with property pm,n can have.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE