最大度为3的图的L(2,1)-边标号的有效算法  

Efficient Algorithm for L(2,1)-edge-labelling of Graphs with Maximum Degree 3

作　　者：叶林 李涌 YE Lin;LI Yong(No.1 Technician College of Taizhou,Taizhou,Zhejiang 317500)

机构地区：[1]台州第一技师学院,浙江台州317500

出　　处：《绍兴文理学院学报》2020年第2期115-120,共6页Journal of Shaoxing University

摘　　要：主要研究最大度为3的图的L(2,1)-边标号.通过对图的分解,可以分成圈集和森林,再依次标号圈集和森林.给出了一个有效算法在线性时间之内可以找到图的16-L(2,1)-边标号,同时验证了Griggs和Yeh猜想对于该类图成立.In this paper,we consider the L(2,1)-edge-labelling of graphs ofmaximum degree 3.The graph can be divided into circles and forests which can then be labelled.We present a linear time algorithm to find a 16-L(2,1)-edge-labelling and verify the correctness of conjecture of Griggs and Yeh forthe graph class considered.

关 键 词：边-L(2 1)-标号 标号数 最大度 有效算法 

分 类 号：O157.5[理学—数学]