Mathematics

L(2, 1)-labelling of Halin graphs with a maximum degree of seven

  • CHEN Xiao-feng ,
  • WANG Yi-qiao
Expand
  • School of Management, Beijing University of Chinese Medicine, Beijing 100029, China

Received date: 2018-05-07

  Online published: 2019-01-24

Abstract

A Halin graph is a plane graph G=TC, 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.

Cite this article

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

References

[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.
Outlines

/