Bandwidth versus Bandsize
Bandwidth versus Bandsize
The bandwidth (bandsize) of a graph G is the minimum, over all bijections u: V(G) → {1,2,…,|V(G)|}, of the greatest difference (respectively the number of distinct differences) |u(v)—u(w)| for vw ɛE(G). We show that a graph on n vertices with bandsize k has bandwidth between k and cn1-1/n, and that …