The relationship between the graphical invariants bandwidth and number of edges is considered. Bounds, some sharp and others improvements of known results, are given for the nznber of edges of graphs having a given bandwidth.
An important invariant of undirected graphs having no loops or multiple edges is the ban&vi&h [3] which can be defined as follows. For a graph G = (V, E) with IV1 =p, an onto function f : V+ { 1,2, . . . , p} is a numbering of G. If e = {u, v} E E, If(u) -f(v)1 is the (edge) value of e induced by f 2nd the maximum such value is designated Bf(G). The bandwidth B = B(G) is then given by min{Bf(G): f is a numbering of G}. A bandwidth numbering f is a numbering such that Bf(G) = B(G).
Bandwidth is one of thirty-six invariants incorporated into the software system INGRID (INteractive GRaph Invariant Delimiter) developed by the authors [l, 51. INGRID permits a user to specify values for some of the invariants. The system then invokes a knowledge base of theorems relating invariants so that it may compute bounds for the remaining invariants in its database. Sometimes the setting of one invariant does not significantly alter the value of some other invariant. This often means that the theory relating the two is weak and research in this area would be fruitful. Chinn observed that setting bandwidth B had little effect on the number of edges e computed by INGRID, and she conjectured that e 2 2B -1. This motivated the work reported here.
We shall be concerned mainly with lower bounds for e, given B, although we also shall briefly consider upper bounds. In Section 2, we develop a general lower bound which immediately leads both to sharp results for the case B sp/2 and to a proof of Chinn's conjecture. Her conjecture was also proved independently by Dewdney [4]. Section 3 treats the apparently more difficult case of B > p/2.