An L(2, 1)-labelling of a graph G is a function from the vertex set V(G) to the set of all nonnegative integers such that │f(u) - f(v)│≥2 if dG(u, v) = 1 and │f(u) - f(v)│ ≥ 1 if dG(u, v) = 2. Th...An L(2, 1)-labelling of a graph G is a function from the vertex set V(G) to the set of all nonnegative integers such that │f(u) - f(v)│≥2 if dG(u, v) = 1 and │f(u) - f(v)│ ≥ 1 if dG(u, v) = 2. The L(2, 1)-labelling problem is to find the smallest number, denoted by A(G), such that there exists an L(2, 1)-labelling function with no label greater than it. In this paper, we study this problem for trees. Our results improve the result of Wang [The L(2, 1)-labelling of trees, Discrete Appl. Math. 154 (2006) 598-603].展开更多
基金National Natural Science Foundation of China(No.10671074 and No.60673048)Natural Science Foundation of Education Ministry of Anhui Province(No.KJ2007B124 and No.2006KJ256B)
基金Supported by the National Natural Science Foundation of China (No. 10971248,11101057)Anhui Provincial Natural Science Foundation (No. 10040606Q45)Postdoctoral Science Foundation of Jiangsu Provinc (No.1102095C)
文摘An L(2, 1)-labelling of a graph G is a function from the vertex set V(G) to the set of all nonnegative integers such that │f(u) - f(v)│≥2 if dG(u, v) = 1 and │f(u) - f(v)│ ≥ 1 if dG(u, v) = 2. The L(2, 1)-labelling problem is to find the smallest number, denoted by A(G), such that there exists an L(2, 1)-labelling function with no label greater than it. In this paper, we study this problem for trees. Our results improve the result of Wang [The L(2, 1)-labelling of trees, Discrete Appl. Math. 154 (2006) 598-603].