On L(d,1)-labelling of Trees

Document Type : Original Scientific Paper

Authors

1 Faculty of Mechanical Engineering, University of Maribor, Maribor, Slovenia

2 Faculty of Mechanical Engineering, University of Ljubljana, Ljubljana, Slovenia

Abstract

Given a graph G and a positive integer d, an L(d,1)-labelling of G is a function f that assigns to each vertex of G a non-negative integer such that if two vertices u and v are adjacent, then |f(u)-f(v)|≥ d and if u and v are at distance two, then |f(u)-f(v)|≥ 1. The L(d,1)-number of G, λd(G), is the minimum m such that there is an L(d,1)-labelling of G with f(V)⊆ {0,1,… ,m}. A tree T is of type 1 if λd(T)= Δ +d-1 and is of type 2 if λd(T)≥ Δ+d. This paper provides sufficient conditions for λd(T)=Δ+d-1 generalizing the results of Wang [11] and Zhai, Lu, and Shu [12] for L(2,1)-labelling.

Keywords

References

[1] T. Calamoneri, The L(h,k)-labeling problem: An updated survey and annotated bibliography, Comput. J. 54 (8) (2011) 1344 - 1371.
[2] G. J. Chang and D. Kuo, The L(2,1)-labeling problem on graphs, SIAM J. Discrete Math. 9 (2) (1996) 309 - 316.
[3] G. J. Chang, W. -T. Ke, D. Kuo, D. D. -F. Liu and R. K. Yeh, On L(d,1)-labeling of graphs, Discrete Math. 220 (2000) 57 - 66.
[4] G. J. Chang and C. Lu, Distance-two labelings of graphs, European J. Combin. 24 (2003) 53 - 58.
[5] J. Georges, D. Mauro and M. Whittlesey, Relating path covering to vertex labelings with a condition at distance two, Discrete Math. 135 (1994) 103 -111.
[6] D. Gonçalves, On the L(p,1)-labelling of graphs, Discrete Math. 308 (2008) 1405 - 1414.
[7] J. R. Grigs and R. K. Yeh, Labeling graphs with a condition at distance 2, SIAM J. Discrete Math. 5 (1992) 586 - 595.
[8] E. Jonck, J. H. Hattingh and C. J. Ras, A characterization of λd;1-minimal trees and other attainable classes, Discrete Math. 309 (2009) 2340 - 2348.
[9] J. S. -T. Juan, D. D. -F. Liu and L. -Y. Chen, L(j,k)-labelling and maximum ordering-degrees for trees, Discrete Appl. Math. 158 (2010) 692 - 698.
[10] D. Liu and R. K. Yeh, On distance two labelings of graphs, Ars. Combin. 47 (1997) 13 - 22.
[11] W. Wang, The L(2,1)-labeling of trees, Discrete Appl. Math. 154 (2006) 598 - 603.
[12] M. Zhai, C. Lu and J. Shu, A note on L(2,1)-labeling of Trees, Acta. Math. Appl. Sin. 28 (2012) 395 - 400.
[13] J. Zhu, Z. Bu, M. P. Pardalos, H. Du, H. Wang and B. Liu, Optimal channel assignment and L(p,1)-labeling, J. Global Optim. 72 (2018) 539 - 552.


Mathematics Interdisciplinary Research
Volume 5, Issue 2
June 2020
Pages 87-102

Files

Share

How to cite

Statistics