##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 684.05043

**Autor: ** Erdös, Paul; Hell, P.; Winkler, P.

**Title: ** Bandwidth versus bandsize. (In English)

**Source: ** Graph theory in memory of G. A. Dirac, Pap. Meet., Sandbjerg/Den. 1985, Ann. Discrete Math. 41, 117-129 (1989).

**Review: ** [For the entire collection see Zbl 656.00008.]

After introducing the notions numbering of a graph, width of a numbering, bandwidth and bandsize of a graph, the three authors prove that for fixed integer k, a graph G with n vertices and bandsize k has bandwidth only O(n^{1-1/k}). Moreover, they can show that this bound is best possible. They finish their investigations by comparing the bandwidth and bandsize of random graphs, by finding a lower bound for the bandsize, and by giving a long list of references concerning this topic.

**Reviewer: ** R.Bodendiek

**Classif.: ** * 05C99 Graph theory

05C80 Random graphs

**Keywords: ** bandwidth; bandsize; random graphs

**Citations: ** Zbl 656.00008

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag