关于图的L(d,1)-标号问题  

The L(d,1)-labeling problem on graphs

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

机构地区：[1]哈尔滨工业大学深圳研究生院 [2]山东大学数学研究所,山东济南250100

出　　处：《高校应用数学学报（A辑）》2004年第B12期561-566,共6页Applied Mathematics A Journal of Chinese Universities(Ser.A)

基　　金：博士后科研启动基金资助项目(0203006211)

摘　　要：图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有maxf(v)v∈V(G)=k的L(2,1)-标号中的最小数k.Griggs和Yeh猜想对最大度为Δ的一般图G,有λ(G)≤Δ2.此文研究了作为L(2,1)-标号问题的推广的L(d,1)-标号问题,并得出了平面三角剖分图、立体四面体剖分图、平面近四边形剖分图的L(d,1)-标号的上界,作为推论证明了对上述几类图该猜想成立.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, the L（d,1）-labeling is studied and the upper bounds of λd（G） of plane triangulation graph, solid tetrahedron subdivision graph,plane near quadrangle subdivision graph are derived, and as corollaries,the conjecture is proved to be true for the above several classes of graphs.

关 键 词：L(2 1)-标号 T-染色 平面三角剖分图 立体四面体剖分图 平面近四边形剖分图 

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