On the Additive Bandwidth of Graphs

Abstract

A $numbering$ of a graph $G=(V,E)$ is a bijection $f:V\to \{1,2,\dots ,p\}$ where $|V|=p$. The $additivebandwidthofnumbering$ $f$ is $B^{+}(G,f)=max\{|f(u)+f(v)–(p+1)|:uv\in E\}$, and the $additivebandwidth$ of $G$ is $B^{+}(G)=min\{B^{+}(G,f):f\text{ a numbering of }G\}$. Labeling $V$ by a numbering which yields $B^{+}(G)$ has the effect of causing the $1$’s in the adjacency matrix of $G$ to be placed as near as possible to the main counterdiagonal, a fact which offers potential storage savings for some classes of graphs. Properties of additive bandwidth are discussed, including relationships with other graphical invariants, its value for cycles, and bounds on its value for extensions of full $k$-ary trees.