Korean J. Math.  Vol 23, No 4 (2015)  pp.607-618
DOI: https://doi.org/10.11568/kjm.2015.23.4.607

Distance two labeling on the square of a cycle

Xiaoling Zhang


An $L(2,1)$-labeling of a graph $G$ is a function $f$ from the vertex set $V(G)$ to the set of all non-negative integers such that $|f(u)-f(v)|\geq 2$ if $d(u,v)=1$  and $|f(u)-f(v)|\geq 1$ if $d(u,v)=2$. The $\lambda$-number  of $G$, denoted $\lambda(G)$, is the smallest number $k$ such that $G$ admits an $L(2, 1)$-labeling with $k=\max\{f(u)|u\in V(G)\}$. In this paper, we consider the square of a cycle and provide exact value for its $\lambda$-number. In addition, we also completely determine its edge span.


Channel assignment; $L(2,1)$-labeling; square of a cycle; $\lambda$-number; edge span.

Subject classification



Research supported by Science Foundation of the Fujian Province, China (No. 2015J05013).

Full Text:



T. Calamoneri and R. Petreschi, L(h, 1)-labeling subclasses of planar graphs, J. Parall. Distrib. Comput. 64 (2004), 414–426. (Google Scholar)

T. Calamoneri, Exact solution of a class of frequency assignment problems in cellular networks and other regular grids, Theor. Comput. Sci. 8 (2006), 141–158. (Google Scholar)

T. Calamoneri, The L(h, k)-labelling problem: an updated survey and annotated bibliography, Computer J. 54 (2011), 1344–1371. (Google Scholar)

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

J.P. Georges, D.W. Mauro and M.A. Whittlesey, Relating path coverings to vertex labellings with a condition at distance two, Discrete Math. 135 (1994), 103–111. (Google Scholar)

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

J.R. Griggs, Real number channel assignments with distance conditions, SIAM J. Discrete Math. 20 (2006), 302–327. (Google Scholar)

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

J. van den Heuvel, R.A. Leese and M.A. Shepherd, Graph labelling and radio channel assignment, J. Graph Theory 29 (1998), 263–283. (Google Scholar)

L.-H. Huang and G.J. Chang, L(h,k)-labelings of Hamming graphs, Discrete Math. 309 (2009), 2197–2201. (Google Scholar)

N. Karst, J. Oehrlein, D.S. Troxell and J. Zhu, The minimum span of L(2, 1)- labelings of generalized flowers, Discrete Appl. Math. 181 (2015), 139–151. (Google Scholar)

M. Kochol, Tension polynomials of graphs, J. Graph Theory 3 (2002), 137–146. (Google Scholar)

A. Kohl, Knotenf ̈arbungen mit Abstandsbedingungen, Dissertation, TU Bergakademie Freiberg, Germany, 2006(in German). (Google Scholar)

D. Korˇze and A. Vesel, L(2,1)-labeling of strong products of cycles, Inform. Process Lett. 94 (2005),183–190. (Google Scholar)

S. Paul, M. Pal and A. Pal, L(2, 1)-Labeling of Permutation and Bipartite Permutation Graphs, Math. Comput. Sci. 9 (2015),113–123. (Google Scholar)

Z. Shao and R.K. Yeh, The L(2,1)-labeling and operations of graphs, IEEE Trans. Circuits Syst. I Fund. Theory Appl. 52 (2005), 668–671. (Google Scholar)

Z. Shao and R.K. Yeh, The L(2, 1)-labeling on planar graphs, Appl. Math. Lett. 20 (2007), 222–226. (Google Scholar)

W.F. Wang, The L(2,1)-labelling of trees, Discrete Appl. Math. 154 (2007), 598–603. (Google Scholar)

R.K. Yeh, A survey on labeling graphs with a condition at distance two, Discrete Math. 306 (2006), 1217–1231. (Google Scholar)

R.K. Yeh, The edge span of distance two labelings of graphs, Taiwanese J. Math. 4 (2000), 675–683. (Google Scholar)

X.L. Zhang and J.G. Qian, L(p, q)-labeling and integer tension of a graph embedded on torus, J. Combin. Optim. 2014, Published on-line, DOI: 10.1007/s10878- 014-9714-4. (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