A Halin graph is a plane graph G=T ∪ C, where T is a tree with no vertex of degree 2 and at least one vertex of degree 3 or more, and C is a cycle connecting the leaves of T in the cyclic order determined by the drawing of T. After structural analysis of Halin graphs, we show that the L(2,1)-labelling number of every Halin graph G with a maximum degree 7 is at most 10.
CHEN Xiao-feng
,
WANG Yi-qiao
. L(2, 1)-labelling of Halin graphs with a maximum degree of seven[J]. Journal of East China Normal University(Natural Science), 2019
, 2019(1)
: 39
-47,57
.
DOI: 10.3969/j.issn.1000-5641.2019.01.005
[1] HALE W K. Frequency assignment:Theory and applications[J]. Proceedings of the IEEE, 1980, 68(12):1497-1514.
[2] GRIGGS J R, YEH R K. Labelling graphs with a condition at distance 2[J]. SIAM J Discrete Math, 1992, 5:586-595.
[3] CHANG G J, KUO D. The L(2, 1)-labelling problem on graphs[J]. SIAM J Discrete Math, 1996, 9:309-316.
[4] GONÇ ALVES D. On the L(p, 1)-labelling of graphs[J]. Discrete Math and Theoret Comput Sci AE, 2005:81-86.
[5] HAVET F, REED B, SERENI J S. Griggs and Yeh's conjecture and L(p, 1)-labeling[J]. SIAM J Discrete Math, 2012:145-168.
[6] VAN DEN HEUVEL J, MCGUINNESS S. Coloring the square of a planar graph[J]. Journal of Graph Theory, 2003, 42:110-124.
[7] MOLLOY M, SALAVATIPOUR M R. A bound on the chromatic number of the square of a planar graph[J]. Journal of Combinatorial Theory Series B, 2005, 94:189-213.
[8] WANG W F, LIH K W. Labelling planar graphs with conditions on girth and distance two[J]. SIAM J Discrete Math, 2003, 17(2):264-275.
[9] 王永强, 任韩. Halin图的消圈数及点染色问题[J]. 华东师范大学学报(自然科学版), 2016(6):65-70.
[10] WANG Y. Distance two labeling of Halin graphs[J]. Ars Combinatoria, 2014, 114:331-343.
中国综合性科技类核心期刊(北大核心)