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