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(n1-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