Change in Additive Bandwidth When an Edge is Added

Abstract

Let \(G = (V,E)\) be an n-vertex graph and \(f : V \rightarrow \{1,2,\ldots,n\}\) be a bijection. The additive bandwidth of \(G\), denoted \(B^+(G)\), is given by \(B^+(G) = \min_{f} \max_{u,v\in E} |f(u) + f(v) – (n+1)|\), where the minimum ranges over all possible bijections \(f\). The additive bandwidth cannot decrease when an edge is added, but it can increase to a value which is as much as three times the original additive bandwidth. The actual increase depends on \(B^+(G)\) and n and is completely determined.