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.

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
Mots-clés : Bandwidth, edge-bandwidth, triangular grid, lower bound, upper bound

Affiliations des auteurs :

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

@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://www.numdam.org/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://www.numdam.org/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://www.numdam.org/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. http://www.numdam.org/articles/10.1051/ita/2014027/

Bibliographie
Cité par

R. Akhtar, T. Jiang and D. Pritikin, Edge-bandwidth of the triangular grid. Electron. J. Combin. 14 (2007) #R67. | MR | Zbl

R. Akhtar, T. Jiang and Z. Miller, Asymptotic determination of edge-bandwidth of grids and Hamming graphs. SIAM J. Discrete Math. 22 (2008) 425–449. | DOI | MR | Zbl

J. Balogh, D. Mubayi and A. Pluhár, On the edge-bandwidth of graph products. Theoret. Comput. Sci. 359 (2006) 43–57. | DOI | MR | Zbl

J.A. Bondy and U.S.R. Murty, Graph Theory. Springer-Verlag, Berlin (2008). | MR | Zbl

T. Calamoneri, A. Massiui and I. Vrťo, New results on edge-bandwidth. Theoret. Comput. Sci. 309 (2003) 503–513. | DOI | MR | Zbl

P.Z. Chinn, J. Chvátalová, A.K. Dewdney and N.E. Gibbs, The bandwidth problem for graphs and matrices – A survey. J. Graph Theory 6 (1982) 223–254. | DOI | MR | Zbl

J. Chvátalová, Optimal labeling of a product of two paths. Discrete Math. 11 (1975) 249–253. | DOI | MR | Zbl

J. Diaz, J. Petit and M. Serna, A survey of graph layout problems. ACM Comput. Surveys 34 (2002) 313–356. | DOI

D. Eichhorn, D. Mubayi, K. O’Bryant and D. West, The edge-bandwidth of theta graphs. J. Graph Theory 35 (2000) 89–98. | DOI | MR | Zbl

L.H. Harper, Optimal numbering and isoperimetric problems on graphs. J. Combin. Theory 1 (1966) 385–393. | DOI | MR | Zbl

R. Hochberg, C. Mcdiarmid and M. Saks, On the bandwidth of triangulated triangles. Discrete Math. 138 (1995) 261–265. | DOI | MR | Zbl

T. Jiang, D. Mubayi, A. Shastri and D. West, Edge-bandwidth of graphs. SIAM J. Discrete Math. 12 (1999) 307–316. | DOI | MR | Zbl

L. Lin, Y. Lin and D. West, Cutwidth of triangulated grids. Discrete Math. 331 (2014) 89–92. | DOI | MR | Zbl

O. Pikhurko and J. Wojciechowski, Edge-bandwidth of grids and tori. Theoret. Comput. Sci. 369 (2006) 35–43. | DOI | MR | Zbl

Cité par Sources :