New bounds on the edge-bandwidth of triangular grids^∗

¹ School of Electronics and Information Engineering, Tongji University, Shanghai 200092, P.R. China.
linlan@tongji.edu.cn
² The Key Laboratory of Embedded System and Service Computing, Ministry of Education, Tongji University, Shanghai 200092, P.R. China.
³ Department of Mathematics, Zhengzhou University, Zhengzhou 450001, P.R. China.
linyixun@zzu.edu.cn

Received: 23 March 2014
Accepted: 8 October 2014

Abstract

The edge-bandwidth of a graph G is the bandwidth of the line graph of G. Determining the edge-bandwidth B^′(T_n) of triangular grids T_n is an open problem posed in 2006. Previously, an upper bound and an asymptotic lower bound were found to be 3n − 1 and 3n − o(n) respectively. In this paper we provide a lower bound 3n − ⌈ n/ 2 ⌉ and show that it gives the exact values of B^′(T_n) for 1 ≤ n ≤ 8 and n = 10. Also, we show the upper bound 3n − 5 for n ≥ 10.