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

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$.


L(3,2,1)-labeling; cartesian products;

Full Text:



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.

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

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).

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

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

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

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

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.

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

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

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.

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.

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

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

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.

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

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

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

DOI: http://dx.doi.org/10.11568/kjm.2017.25.2.279


  • There are currently no refbacks.

ISSN: 1976-8605 (Print), 2288-1433 (Online)

Copyright(c) 2013 By The Kangwon-Kyungki Mathematical Society, Department of Mathematics, Kangwon National University Chuncheon 21341, Korea Fax: +82-33-259-5662 E-mail: kkms@kangwon.ac.kr