Edge-bandwidth of grids and tori

AbstractThe edge-bandwidth of a graph G is the smallest number B′ for which there is a bijective labeling of E(G) with {1,…,e(G)} such that the difference between the labels at any adjacent edges is at most B′. Here we compute the edge-bandwidth for rectangular grids:B′(Pm⊕Pn)=2min(m,n)-1ifmax(m,n)≥3,where ⊕ is the Cartesian product and Pn denotes the path on n vertices. This settles a conjecture of Calamoneri et al. [New results on edge-bandwidth, Theoret. Comput. Sci. 307 (2003) 503–513]. We also compute the edge-bandwidth of any torus (a product of two cycles) within an additive error of 5