##
**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