关于几类图的L(2,1)标号问题

图G的L( 2 ,1 )标号是一个从顶点集V(G)到非负整数集的函数f(x) ,使得若d(x ,y) =1 ,则｜f(x) -f(y) ｜≥ 2 ;若d(x ,y) =2 ,则｜f(x) -f(y) ｜≥ 1 .图G的L( 2 ,1 ) 标号数λ(G)是使得G有max{f(v) ∶v∈V(G) }=k的L( 2 ,1 )标号中的最小数k .Griggs和Yeh猜想对最大度为Δ的一般图G ,有λ(G) ≤Δ2 .本文给出了Kneser图 ,Mycieklski图 ,Descartes图 ,Halin图的λ值的上界 ,并证明了上述猜想对以上几类图成立

The L(2,1)-labeling Problem on Several Classes of Graphs

An L(2,1) labeling of a graph G is a function f from the vertex set V(G) to the set of all nonnegative integers such that | f(x) - f(y)|≥ 2 ifd(x,y) = 1 and |f(x) - f(y) |≥ 1 if d(x,y) = 2. The L(2,1)- labeling number λ(G) of G is the smallest number k such that G has an L(2,1)-labeling with max{ f(v): v ∈ V(G)) = k. Griggs and Yeh conjecture thatλ(G) ≤△2 for any simple graph with maximum degree△. In this paper, we derive the upper bounds of λ(G) of Kneser graph,Mycielski graph,Descartes graph, Halin graph, and prove that the conjecture is true for the above several classes of graphs.