Shortness Exponents of Families of Graphs.
Abstract
Let v(G) denote the number of vertices of a graph G and h(G) the maximal length of a simple circuit in G. A number alpha is a shortness exponent for a family G of graphs provided there exists a real beta and a sequence G sub n of graphs in G such that V sub n = v(G sub n) approaches infinity for n to infinity and h(G sub n) < or = beta(v sub n sup alpha). Ten years ago the author and T. S. Motzkin established that alpha = 1 - (2 sup (-17)) is a shortness exponent for the family of all 3-connected, 3-valent planar graphs. In the present report the author obtains strengthenings and generalizations of this result and of results of Moon and Moser, Walther, Jucovic and others. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1972
- Accession Number
- AD0739717
Entities
People
- Branko Gruenbaum
Organizations
- University of Washington