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

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名

邮箱

手机号码

标题

留言内容

验证码

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

基金项目:

国家自然科学基金 11671053

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

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

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