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

Article Sidebar

PDF
Published: Dec 30, 2015
Keywords:
Channel assignment, $L(2, 1)$-labeling, square of a cycle, $\lambda$-number, edge span.
Mathematics Subject Classification:
05C15

Main Article Content

Xiaoling Zhang
College of Mathematics and Computer Science Quanzhou Normal University Quanzhou 362000, Fujian, P.R. China

Abstract

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.


Article Details

Supporting Agencies

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

References

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

[2] 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

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

[4] 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

[5] 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

[6] 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

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

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

[9] 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

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

[11] 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

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

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

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

[15] 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

[16] 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

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

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

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

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

[21] 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