Geodesic
Characterization Results for the L(2, 1, 1)-Labeling Problem on Trees
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 611-622.

Voir la notice de l'article provenant de la source Library of Science

An L(2, 1, 1)-labeling of a graph G is an assignment of non-negative integers (labels) to the vertices of G such that adjacent vertices receive labels with difference at least 2, and vertices at distance 2 or 3 receive distinct labels. The span of such a labelling is the difference between the maximum and minimum labels used, and the minimum span over all L(2, 1, 1)-labelings of G is called the L(2, 1, 1)-labeling number of G, denoted by λ2,1,1(G). It was shown by King, Ras and Zhou in [The L(h, 1, 1)-labelling problem for trees, European J. Combin. 31 (2010) 1295–1306] that every tree T has Δ2(T) − 1 ≤ λ2,1,1(T) ≤ Δ2(T), where Δ2(T) = maxuv∈E(T)(d(u) + d(v)). And they conjectured that almost all trees have the L(2, 1, 1)-labeling number attain the lower bound. This paper provides some sufficient conditions for λ2,1,1(T) = Δ2(T). Furthermore, we show that the sufficient conditions we provide are also necessary for trees with diameter at most 6.
Keywords: tree, diameter, L(2, 1, 1)-labeling 
@article{DMGT_2017_37_3_a8,
     author = {Zhang, Xiaoling and Deng, Kecai},
     title = {Characterization {Results} for the {L(2,} 1, {1)-Labeling} {Problem} on {Trees}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {611--622},
     publisher = {mathdoc},
     volume = {37},
     number = {3},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a8/}
}
TY  - JOUR
AU  - Zhang, Xiaoling
AU  - Deng, Kecai
TI  - Characterization Results for the L(2, 1, 1)-Labeling Problem on Trees
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 611
EP  - 622
VL  - 37
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a8/
LA  - en
ID  - DMGT_2017_37_3_a8
ER  - 
%0 Journal Article
%A Zhang, Xiaoling
%A Deng, Kecai
%T Characterization Results for the L(2, 1, 1)-Labeling Problem on Trees
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 611-622
%V 37
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a8/
%G en
%F DMGT_2017_37_3_a8
Zhang, Xiaoling; Deng, Kecai. Characterization Results for the L(2, 1, 1)-Labeling Problem on Trees. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 611-622. http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a8/

[1] T. Calamoneri, The L(h, k)-labelling problem: an updated survey and annotated bibliography, Comput. J. 54 (2011) 1344–1371. doi:10.1093/comjnl/bxr037

[2] G.J. Chang and D. Kuo, The L(2, 1)-labeling problem on graphs, SIAM J. Discrete Math. 9 (1996) 309–316. doi:10.1137/S0895480193245339

[3] M. Chia, D. Kuo, H. Liao, C. Yang and R.K. Yeh, L(3, 2, 1)-labeling of graphs, Taiwanese J. Math. 15 (2011) 2439–2457.

[4] J. Fiala, P.A. Golovach, J. Kratochvíl, B. Lidický and D. Paulusma, Distance three labelings of trees, Discrete Appl. Math. 160 (2012) 764–779. doi:10.1016/j.dam.2011.02.004

[5] J.P. Georges and D.W. Mauro, Labeling trees with a condition at distance two, Discrete Math. 269 (2003) 127–148. doi:10.1016/S0012-365X(02)00750-1

[6] P.A. Golovach, B. Lidický and D. Paulusma, L(2, 1, 1)-labeling is NP-complete for trees, in: Theory and Applications of Models of Computation, Lecture Notes in Comput. Sci. 6108 (2010) 211–221. doi:10.1007/978-3-642-13562-0_20

[7] J.R. Griggs and R.K. Yeh, Labelling graphs with a condition at distance 2, SIAM J. Discrete Math. 5 (1992) 586–595. doi:10.1137/0405048

[8] W.K. Hale, Frequency assignment: Theory and applications, Proc. IEEE 68 (1980) 1497–1514. doi:10.1109/PROC.1980.11899

[9] T. Hasunuma, T. Ishii, H. Ono and Y. Uno, A linear time algorithm for L(2, 1)-labeling of trees, Algorithmica 66 (2013) 654–681. doi:10.1007/s00453-012-9657-z

[10] B. Kim, B. Song and W. Hwang, Distance three labelings for direct products of three complete graphs, Taiwanese J. Math. 17 (2013) 207–219. doi:10.11650/tjm.17.2013.1909

[11] D. King, C.J. Ras and S. Zhou, The L(h, 1, 1)-labelling problem for trees, European J. Combin. 31 (2010) 1295–1306. doi:10.1016/j.ejc.2009.11.006

[12] W.-F. Wang, The L(2, 1)-labelling of trees, Discrete Appl. Math. 154 (2006) 598–603. doi:10.1016/j.dam.2005.09.007

[13] R.K. Yeh, A survey on labeling graphs with a condition at distance two, Discrete Math. 306 (2006) 1217–1231. doi:10.1016/j.disc.2005.11.029

[14] S. Zhou, A distance-labelling problem for hypercubes, Discrete Appl. Math. 156 (2008) 2846–2854. doi:10.1016/j.dam.2007.11.018