Erdős, Paul; Hell, P.; Winkler, P. 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 Cited in 5 Documents MSC: 05C99 Graph theory 05C80 Random graphs (graph-theoretic aspects) Keywords:bandwidth; bandsize; random graphs Citations:Zbl 0656.00008 PDFBibTeX XML