## Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  829.05055
Autor:  Alavi, Yousef; Liu, Jiuqiang; McCanna, Joseph; Erdös, Paul
Title:  On the minimum size of graphs with a given bandwidth. (In English)
Source:  Bull. Inst. Comb. Appl. 6, 22-32 (1992).
Review:  Given an integer B > 0, what is the minimum number m(n,B) of edges required for a graph of order n and bandwidth B? For B \leq \lfloor n/2 \rfloor the exact value of m(n,B) has been determined. However, for B > \lfloor n/2 \rfloor it seems difficult to evaluate m(n,B) and there are upper and lower bounds for it. Here we give better bounds.
Classif.:  * 05C78 Graph labelling
68R10 Graph theory in connection with computer science
05C35 Extremal problems (graph theory)
Keywords:  optimal numbering; NP-complete; bandwidth; bounds

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag