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

CHEN Xiao-feng; WANG Yi-qiao

doi:10.3969/j.issn.1000-5641.2019.01.005

Issue 1

Jan. 2019

Turn off MathJax

Article Contents

Article Navigation > Journal of East China Normal University (Natural Sciences) > 2019 > (1): 39-47, 57

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 Sciences), 2019, (1): 39-47, 57. doi: 10.3969/j.issn.1000-5641.2019.01.005

Citation:

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 Sciences), 2019, (1): 39-47, 57. doi: 10.3969/j.issn.1000-5641.2019.01.005

Citation:

PDF( 613 KB)

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

doi: 10.3969/j.issn.1000-5641.2019.01.005

CHEN Xiao-feng,
WANG Yi-qiao^,

School of Management, Beijing University of Chinese Medicine, Beijing 100029, China

Received Date: 2018-05-07
Publish Date: 2019-01-25

Abstract

Abstract

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.
- Halin graph,
- L(2, 1)-labelling,
- maximum degree

FullText(HTML)

References(10)

References

[1]	HALE W K. Frequency assignment:Theory and applications[J]. Proceedings of the IEEE, 1980, 68(12):1497-1514. doi: 10.1109/PROC.1980.11899
[2]	GRIGGS J R, YEH R K. Labelling graphs with a condition at distance 2[J]. SIAM J Discrete Math, 1992, 5:586-595. doi: 10.1137/0405048
[3]	CHANG G J, KUO D. The L(2, 1)-labelling problem on graphs[J]. SIAM J Discrete Math, 1996, 9:309-316. doi: 10.1137/S0895480193245339
[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. http://dl.acm.org/citation.cfm?id=2340072
[6]	VAN DEN HEUVEL J, MCGUINNESS S. Coloring the square of a planar graph[J]. Journal of Graph Theory, 2003, 42:110-124. doi: 10.1002/(ISSN)1097-0118
[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. doi: 10.1016/j.jctb.2004.12.005
[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. doi: 10.1137/S0895480101390448
[9]	王永强, 任韩. Halin图的消圈数及点染色问题[J].华东师范大学学报(自然科学版), 2016(6):65-70. doi: 10.3969/j.issn.1000-5641.2016.06.006
[10]	WANG Y. Distance two labeling of Halin graphs[J]. Ars Combinatoria, 2014, 114:331-343.