Accession Number : AD0739717

Title :   Shortness Exponents of Families of Graphs.

Descriptive Note : Technical rept.,

Corporate Author : WASHINGTON UNIV SEATTLE DEPT OF MATHEMATICS

Personal Author(s) : Gruenbaum,Branko

Report Date : APR 1972

Pagination or Media Count : 29

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)

Descriptors :   (*GRAPHICS, THEOREMS), MAPPING(TRANSFORMATIONS), CIRCUITS, TOPOLOGY

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE