RAIRO-Theor. Inf. Appl.
Volume 49, Number 1, January-March 2015
|Page(s)||47 - 60|
|Published online||18 February 2015|
New bounds on the edge-bandwidth of triangular grids∗
School of Electronics and Information Engineering, Tongji
2 The Key Laboratory of Embedded System and Service Computing, Ministry of Education, Tongji University, Shanghai 200092, P.R. China.
3 Department of Mathematics, Zhengzhou University, Zhengzhou 450001, P.R. China.
Received: 23 March 2014
Accepted: 8 October 2014
The edge-bandwidth of a graph G is the bandwidth of the line graph of G. Determining the edge-bandwidth B′(Tn) of triangular grids Tn 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′(Tn) for 1 ≤ n ≤ 8 and n = 10. Also, we show the upper bound 3n − 5 for n ≥ 10.
Mathematics Subject Classification: 05C78 / 68M10 / 68R10
Key words: Bandwidth / edge-bandwidth / triangular grid / lower bound / upper bound
© EDP Sciences 2015
Initial download of the metrics may take a while.