Korean J. Math. Vol. 25 No. 2 (2017) pp.279-301
DOI: https://doi.org/10.11568/kjm.2017.25.2.279

$L(3,2,1)$-labeling for Cylindrical grid: the cartesian product of a path and a cycle

Main Article Content

Byeong Moon Kim
Woonjae Hwang
Byung Chul Song


An $L(3,2,1)$-labeling for the graph $G=(V,E)$ is an assignment $f$ of a label to each vertices of $G$ such that $|f(u)-f(v)| \geq 4-k$ when $\textrm{dist}(u,v)=k\leq3$. The $L(3,2,1)$-labeling number, denoted by $\lambda_{3,2,1}(G)$, for $G$ is the smallest number $N$ such that there is an $L(3,2,1)$-labeling for $G$ with span $N$.

In this paper, we compute the $L(3,2,1)$-labeling number $\lambda_{3,2,1}(G)$ when $G$ is a cylindrical grid, which is the cartesian product $P_{m}\square C_{n}$ of the path and the cycle, when $m\geq 4$ and $ n\geq 138$. Especially when $n$ is a multiple of $4$, or $m=4$ and $n$ is a multiple of $6$, then we have $\lambda_{3,2,1}(G)=11$. Otherwise $\lambda_{3,2,1}(G)=12$.

Article Details


[1] A. A. Bertossi and M. C. Pinotti, Channel assignment with separation for inter- ference avoidence in weierless networks, IEEE Trans. Parall. Distrib. Syst. 14 (2003), 222–235. Google Scholar

[2] A. A. Bertossi and M. C. Pinotti, Approximate L(δ1 , δ2 , · · · , δt )-coloring of trees and interval graphs, Networks 49 (3) (2007), 204–216. Google Scholar

[3] A. A. Bertossi, M. C. Pinotti and R. Tan, Efficient use of Radio spectrum in weierless networks with channel separation between close stations, dial M for mobility: International ACM workshop, Discrete algorithms and methods for mobile computing, (2000). Google Scholar

[4] T. Calamoneri, The L(h, k)-labeling problem: A survey and annotated bibliogra- phy Comp. J. 49 (2006), 585–608. Google Scholar

[5] T. Calamoneri, The L(h,k)-Labelling Problem: An Updated Survey and Annotated Bibliography, Comp. J. 54 (2011), 1344–1371. Google Scholar

[6] T. Calamoneri, Optimal L(δ1, δ2, 1)- labelling of eight-regular grids, Inform. Process. Lett., 113 (2013), 361–364. Google Scholar

[7] G. J. Chang and D. Kuo, The L(2, 1)-labeling problem on graphs, SIAM J Discrete Math., 9, 309–316 (1996). Google Scholar

[8] M. L. Chia, D. Kuo, H. Liao, C. H. Yang and R. K. Yeh, L(3, 2, 1) labeling of graphs, Taiwan. J. Math. 15 (2011), 2439–2457. Google Scholar

[9] J. R. Griggs and R. K. Yeh, Labeling graphs with a condition at distance two, SIAM J. Discrete Math. 5 (1992), 586–595. Google Scholar

[10] W. K. Hale, Frequency assignment: theory and application, Proc. IEEE 68 (1980), 1497–1514. Google Scholar

[11] B. M. Kim, W. Hwang and B. C. Song, L(3, 2, 1)-labeling for the product of a complete graph and a cycle, Taiwan. J. Math., 19 (2015), 819–848. Google Scholar

[12] B. M. Kim, B. C. Song and W. Hwang, Distance three labelings for direct products of three complete graphs, Taiwan. J. Math. 17 (2013), 207–219. Google Scholar

[13] B. M. Kim, B. C. Song and W. Hwang, Distance three labellings for Kn × K2, Int. J. Comput. Math., 90 (5) (2013), 906–911. Google Scholar

[14] J. Liu and Z. Shao, The L(3, 2, 1)-labeling problem on graphs, Math. Appl. 17 (2004), 596–602. Google Scholar

[15] Z. Shao and A. Vesel, Integer linear programming model and satisfiability test reduction for distance constrained labellings of graphs: the case of L(3,2,1) la- belling for products of paths and cycles, IET Commun. 7 (2013), 715–720. Google Scholar

[16] Z. Shao and A. Vesel, L(3,2,1) -labeling of triangular and toroidal grids, Cent. Eur. J. Oper. Res. 23 (2015), 659–673. Google Scholar

[17] R. K. Yeh, A survey on labeling graphs with a condition two, Disc. Math., 306 (2006)., 1217–123 Google Scholar

[18] S. Zhou, A distance-labelling problem for hypercubes, Discrete Appl. Math. 156 (15) (2008), 2846–2854. Google Scholar