华东师范大学学报（自然科学版） >

2019 , Vol. 2019 >Issue 1: 39 - 47,57

DOI: https://doi.org/10.3969/j.issn.1000-5641.2019.01.005

数学

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

  • 陈晓峰 ,
  • 王艺桥
展开
  • 北京中医药大学 管理学院, 北京 100029
陈晓峰,男,硕士研究生,研究方向为图染色.E-mail:1806381899@qq.com.

收稿日期: 2018-05-07

  网络出版日期: 2019-01-24

基金资助

国家自然科学基金（11671053）

收起

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

Fold

摘要

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

关键词： 哈林图; L(2; 1)-标号; 最大度

本文引用格式

陈晓峰 , 王艺桥 . 最大度为7的哈林图的L(2,1)-标号[J]. 华东师范大学学报（自然科学版）, 2019 , 2019(1) : 39 -47,57 . DOI: 10.3969/j.issn.1000-5641.2019.01.005

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.

Key words： Halin graph; L(2,1)-labelling; maximum degree

参考文献

[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.
Options
文章导航

/

〈 〉