摘要
图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图的λ值的上界 。
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 if d(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.
出处
《应用数学》
CSCD
北大核心
2004年第1期31-36,共6页
Mathematica Applicata
