\(L(2,1)\)-Labeling of Cartesian Product of Complete Bipartite Graph and Path

Sumonta Ghosh, Satyabrata Paul, Anita Pal


An \(L(2,1)\)-labeling problem is a particular case of \(L(h,k)\)-labeling problem. An \(L(2,1)\)-labeling of a graph \(G=(V,E)\) is a function \(f\) from the set of vertices \(V\) to the set of positive integers. For any two vertices \(x\) and \(y\), the label difference \(|f(x)-f(y)|\geq2\) when \(d(x,y)=1\) and \(|f(x)-f(y)|\geq1\) when \(d(x,y)=2\) where \(d(x,y)\) is the distance between the vertices \(x\) and \(y\). In this paper we label the graph which is obtained by Cartesian product between complete bipartite graph and path by \(L(2,1)\)-labeling. We provide upper bound of the label in terms of number of vertices and edges. The bound is linear with respect to the order and size of the graph. This is a very good bound compare to the bound of Griggs and Yeh Conjecture.


\(L(2,1)\)-labeling; Graph labeling; Cartesian product of graphs

Full Text:



H.L. Bodlaender, T. Kloks, R.B. Tan and J.V. Leeuwen, Approximations for (lambda)-colorings of graphs, Comput. J. 47 (2) (2004), 193–204.

T. Calamoneri, S. Caminiti, S. Olariu and R. Petreschi, On the (L(h,k))-labeling of co-comparability graphs and circular-arc graphs, Networks 53 (1) (2009), 27–34.

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

N. Daldosso and L. Pavesi, Nanosilicon, Chapter 1, edited by Vijay Kumar, Elsevier, New York, 2005.

L. Deng, K. He, T. Zhou and C. Li, J. Opt. A: Pure Appl. Opt. 7 (2005), 409.

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

J.P. Georges, D.W. Mauro and M.I. Stein, Labeling products of complete graphs with a condition at distance two, SIAM J. Discrete Math. 14 (2000), 28–35.

D. Gonçalves, On the (L(d,1))-labellinng of graphs, Discret. Math. 308 (2008), 1405–1414.

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

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

T. Hasunuma, T. Ishii, H. Ono and Y. Uno, A linear time algorithm for L(2, 1)-labeling of trees, in Lecture Notes in Computer Science 5757 (2009), 35–46.

F. Havet, B. Reed and J.S. Sereni, (L(2,1))-labeling of graphs, in Proceedings of the 19th Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2008, SIAM, 621–630 (2008).

M. Ito, K. Imakita, M. Fujii and S. Hayashi, J. Appl. Phys. 108 (2010), 063512.

M. Ito, K. Imakita, M. Fujii and S. Hayashi, J. Phys. D: Appl. Phys. 43 (2010), 505101.

P.K. Jha, A. Narayanan, P. Sood, K. Sundaram and V. Sunder, On (L(2,1))-labelings of the Cartesian product of a cycle and a path, Ars Combin. 55 (2000).

P.K. Jha, Optimal (L(2,1))-labeling of Cartesian products of cycles, with an application to independent domination, IEEE Trans. Circuits and Syst. – I 47 (10) (2000), 1531–1534.

P.K. Jha, S. Klavžar and A. Vesel, Optimal (L(2,1))-labelings of certain direct products of cycles and Cartesian products of cycles, Discrete Appl. Math. 152 (2005), 257–265.

S. Klavžar and A. Vesel, Computing graph invariants on rotagraphs using dynamic algorithm approach: the case of (2,1)-colorings and independence numbers, Discrete Appl. Math. 129 (2003), 449–460.

D. Král, R. Skrekovski, A theory about channel assignment problem, SIAM J. Discret. Math. 16 (2003), 426–437.

S. Paul, M. Pal and A. Pal, (L(2,1))-labeling of permutation and bipartite permutation graphs, Math. Comput. Sci. doi:10.1007/s11786-014-0180-2.

A. Petris, F. Pettazzi, E. Fazio, C. Peroz, Y. Chen, V.I. Vlad and M. Bertolotti, J. Optoelectronics & Advanced Materials 8 (2006), 1377.

D. Sakai, Labeling chordal graphs with a condition at distance two, SIAM J. Discret. Math. 7 (1994), 133–140.

C. Schwarza, D.S. Troxellb, (L(2,1))-labelings of Cartesian products of two cycles, Discrete Applied Mathematics 154 (2006), 1522–1540.

M.A. Whittlesey, J.P. Georges and D.W. Mauro, On the number of Qn and related graphs, SIAM J. Discrete Math. 8 (1995), 499–506.

DOI: http://dx.doi.org/10.26713%2Fjims.v9i3.817

eISSN 0975-5748; pISSN 0974-875X