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

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;

Subject classification

05C15, 05C78, 05C38


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. (Google Scholar)

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)

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)

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

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

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

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

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)

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)

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

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)

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)

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)

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

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)

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)

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

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


  • 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