New bounds on the edge-bandwidth of triangular grids

Lin, Lan; Lin, Yixun

doi:10.1051/ita/2014027

Lin, Lan ^1,² ; Lin, Yixun ³

¹ School of Electronics and Information Engineering, Tongji University, Shanghai 200092, P.R. China.
² 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.

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 49 (2015) no. 1, pp. 47-60

Voir la notice de l'article provenant de la source Numdam

Résumé

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 $3 n - 1$ and $3 n - o (n)$ respectively. In this paper we provide a lower bound $3 n - ⌈ n / 2 ⌉$ and show that it gives the exact values of $B^{'} (T_{n})$ for $1 \leq n \leq 8$ and $n = 10$ . Also, we show the upper bound $3 n - 5$ for $n \geq 10$ .

Reçu le : 2014-03-23
Accepté le : 2014-10-08

MR Zbl

DOI : 10.1051/ita/2014027

Classification : 05C78, 68M10, 68R10
Keywords: Bandwidth, edge-bandwidth, triangular grid, lower bound, upper bound

Affiliations des auteurs :

Lin, Lan ^{1, 2} ; Lin, Yixun ³

¹ School of Electronics and Information Engineering, Tongji University, Shanghai 200092, P.R. China.
² 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.

@article{ITA_2015__49_1_47_0,
     author = {Lin, Lan and Lin, Yixun},
     title = {New bounds on the edge-bandwidth of triangular grids},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {47--60},
     publisher = {EDP-Sciences},
     volume = {49},
     number = {1},
     year = {2015},
     doi = {10.1051/ita/2014027},
     mrnumber = {3342172},
     zbl = {1314.05177},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2014027/}
}

TY  - JOUR
AU  - Lin, Lan
AU  - Lin, Yixun
TI  - New bounds on the edge-bandwidth of triangular grids
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2015
SP  - 47
EP  - 60
VL  - 49
IS  - 1
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita/2014027/
DO  - 10.1051/ita/2014027
LA  - en
ID  - ITA_2015__49_1_47_0
ER  -

%0 Journal Article
%A Lin, Lan
%A Lin, Yixun
%T New bounds on the edge-bandwidth of triangular grids
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2015
%P 47-60
%V 49
%N 1
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita/2014027/
%R 10.1051/ita/2014027
%G en
%F ITA_2015__49_1_47_0

Lin, Lan; Lin, Yixun. New bounds on the edge-bandwidth of triangular grids. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 49 (2015) no. 1, pp. 47-60. doi: 10.1051/ita/2014027

Cité par Sources :

Parcourir par

Geodesic

Parcourir par