Edge-bandwidth of grids and tori

The edge-bandwidth of a graph G   is the smallest number B′B′ for which there is a bijective labeling of E(G)E(G) with {1,…,e(G)}{1,…,e(G)} such that the difference between the labels at any adjacent edges is at most B′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 PnPn 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.