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

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

作　　者：邵振东[1] 刘家壮[2] 

机构地区：[1]南京大学数学系,江苏南京210093 [2]山东大学数学研究所,山东济南250100

出　　处：《应用数学》2004年第1期31-36,共6页Mathematica Applicata

摘　　要：图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.

关 键 词：L(2 1)标号 Kneser图 Mycieklski图 Descartes图 HALIN图 

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