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

Authors

  • Sumonta Ghosh 1Department of Mathematics, NIT Durgapur, Durgapur, West Bengal 713209
  • Satyabrata Paul Department of Applied Mathematics with Oceanology and Computer Programming, Vidyasagar University, West Bengal 721102
  • Anita Pal Department of Mathematics, NIT Durgapur, Durgapur, West Bengal 713209

DOI:

https://doi.org/10.26713/jims.v9i3.817

Keywords:

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

Abstract

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.

Downloads

Download data is not yet available.

References

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.

Downloads

Published

2017-10-31
CITATION

How to Cite

Ghosh, S., Paul, S., & Pal, A. (2017). \(L(2,1)\)-Labeling of Cartesian Product of Complete Bipartite Graph and Path. Journal of Informatics and Mathematical Sciences, 9(3), 685–698. https://doi.org/10.26713/jims.v9i3.817

Issue

Vol. 9 No. 3 (2017)

Section

Research Articles

License

Authors who publish with this journal agree to the following terms:
  • Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a CCAL that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
  • Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
  • Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.