最大度为7的哈林图的L(2,1)-标号

详细信息    查看全文 | 推荐本文 |

英文篇名：L(2,1)-labelling of Halin graphs with a maximum degree of seven 作者：陈晓峰 ; 王艺桥 英文作者：CHEN Xiao-feng;WANG Yi-qiao;School of Management, Beijing University of Chinese Medicine; 关键词：哈林图 ; L(2 ; 1)-标号 ; 最大度 英文关键词：Halin graph;;L(2,1)-labelling;;maximum degree 中文刊名：HDSZ 英文刊名：Journal of East China Normal University(Natural Science) 机构：北京中医药大学管理学院; 出版日期：2019-01-25 出版单位：华东师范大学学报(自然科学版) 年：2019 期：No.203 基金：国家自然科学基金(11671053) 语种：中文; 页：HDSZ201901005 页数：10 CN：01 ISSN：31-1298/N 分类号：44-52+62

摘要

哈林图是一个平面图G=T∪C,其中T是嵌入到平面内的不含2度点且至少有一个顶点度大于等于3的树,C是按顺时针顺序依次连接T中的叶形成的圈.通过对哈林图的结构分析,证明了最大度等于7的哈林图的L(2,1)-标号数至多为10.
        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.

引文

[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] GONCALVES 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, l)-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&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.