Journal Version
T. Calamoneri, A. Massini and I. Vrto
Abstract
The edge-bandwidth problem is an analog of the classical bandwidth problem, in which one has to label the edges of a graph by distinct integers such that the maximum difference of labels of any two incident edges is minimized. We prove tight bounds on the edge-bandwidth of hypercube and butterfly graphs and complete $k$-ary trees which extend and improve on previous known results. We also provide an improvement on the upper bound for the bandwidth of butterfly.
PDF Files