Bandwidth versus bandsize. (English) Zbl 0684.05043

Graph theory in memory of G. A. Dirac, Pap. Meet., Sandbjerg/Den. 1985, Ann. Discrete Math. 41, 117-129 (1989).
[For the entire collection see Zbl 0656.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


05C99 Graph theory
05C80 Random graphs (graph-theoretic aspects)


Zbl 0656.00008