On (4, 2)-Labeling of Certain Graphs





Graph labeling, Path, Cycle, Complete bipartite graph, Star graph, Complete graph, Ladder graph


The \((4,2)\)-labeling of a graph \(G\) is a function \(f:V(G)\to {\mathbb{Z}}^+\) such that \(|f(x)-f(y)|\ge 4\) if \(d(x,y)=1\) and \(|f(x)-f(y)|\ge 2\) if \(d(x,y)=2\), for any \(x,y\in V(G)\). In this paper, we label different types of graphs such as paths, cycles, complete and complete bipartite graphs, star graphs and ladder graphs to study the bounds of the span \(\lambda\) of these graphs.


Download data is not yet available.


S. Ghosh and A. Pal, L(3,1)-Labeling of some simple graphs, AMO - Advanced Modeling and Optimization 18(2) (2016), 243 – 248, URL: https://camo.ici.ro/journal/vol18/v18b7.pdf.

J. R. Griggs and R. K. Yeh, Labelling graphs with a condition at distance 2, SIAM Journal on Discrete Mathematics 5(4) (1992), 586 – 595, DOI: 10.1137/0405048.

W. K. Hale, Frequency assignment: Theory and applications, Proceedings of the IEEE 68(12) (1980), 1497 – 1514, DOI: 10.1109/PROC.1980.11899.

N. Khan, M. Pal and A. Pal, L(0,1)-Labeling of cactus graphs, Communications and Network 4(1) (2012), 18 – 29, URL: https://www.scirp.org/pdf/CN20120100002_36636260.pdf.

B. S. Panda and P. Goel, L(2,1)-Labeling of dually chordal graphs and strongly orderable graphs, Information Processing Letters 112(13) (2012), 552 – 556, DOI: 10.1016/j.ipl.2012.04.003.

B. S. Panda and P. Goel, L(2,1)-Labeling of perfect elimination bipartitite graphs, Discrete Applied Mathematics 159(16) (2011), 1878 – 1888, DOI: 10.1016/j.dam.2010.07.008.

S. Paul, M. Pal and A. Pal, L(0,1)-Labeling of permutation graphs, Journal of Mathematical Modelling and Algorithms in Operations Research 14 (2015), 469 – 479, DOI: 10.1007/s10852-015-9280-5.

S. Paul, M. Pal and A. Pal, L(2,1)-Labeling of interval graphs, Journal of Applied Mathematics and Computing 49 (2015), 419 – 432, DOI: 10.1007/s12190-0140846-6.

S. Paul, M. Pal and A. Pal, L(2,1)-Labeling of permutation and bipartite permutation graphs, Mathematics in Computer Science 9 (2015), 113 – 123, DOI: 10.1007/s11786-014-0180-2.

S. Paul, M. Pal and A. Pal, An efficient algorithm to solve L(0,1)-labeling problem on interval graphs, Advanced modeling and Optimization 15(1) (2013), 31 – 43, URL: https://camo.ici.ro/journal/vol15/v15a3.pdf.

C. Schwarz and D. S. Troxell, L(2,1)-Labelings of Cartesian products of two cycles, Discrete Applied Mathematics 154(10) (2006), 1522 – 1540, DOI: 10.1016/j.dam.2005.12.006.

Z. Shao and R. Solis-Oba, L(2,1)-Labelings on the modular product of two graphs, Theoretical Computer Science 487 (2013), 74 – 81, DOI: 10.1016/j.tcs.2013.02.002.




How to Cite

Mishra, A., & Dey, P. C. (2024). On (4, 2)-Labeling of Certain Graphs. Communications in Mathematics and Applications, 14(5), 1529–1535. https://doi.org/10.26713/cma.v14i5.2191



Research Article