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

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

主要研究最大度为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.