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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page