一类积图的局部边路替换图的L(2,1)-

(1. 南通师范高等专科学校， 南通，226007;2. 南通大学理学院，南通，226007)

1 引言

图的距离2标号是经典点着色的一个自然推广.它是在无线电通信波段分配的促动下的自然产物，是无线电通信波段分配问题的图论模式，它的研究成果对波段分配问题起着推进作用，受到多个领域学者们的极大关注.在图的距离2标号中，要求相邻顶点的标号差至少为2，两个距离为2的顶点的标号相差至少为1. 距离2标号的相关研究可参见综述[13-15].其中图的关联图的距离2 标号问题，也即图的(d,1)-全标号问题.1995年，Whittlesty，Georges 和Mauro[1]首先研究了图G的关联图的L(2,1)-标号.2002年，Havet和Yu[2-3]称图G的剖分图(图的剖分图即在图的每条边上再插入一个顶点所得的图)的L(2,1)-标号为图G的(2,1)-全标号，同时将之推广得(d,1)-全标号概念.Havet和Yu 在研究了(d,1)-全标号数的一般规律.图的(d,1)-全标号问题即研究图的关联图的距离2 标号问题.图的关联图可看成图的边-路P3替换图.近几年，关于边-路替换图的标号问题，已经有了一些研究[2-12]. 本文进一步研究路路积图的局部替换图的L(2,1)-标号问题，并完全得到了该图的L(2,1)-标号数.

定义1图G的一个L(2,1)-标号是一个满足下两个条件的映射c:V(G)→(0,1,2，…，k)，

(1)对任意的u,v∈V(G)，若d(u,v)=1，则|c(u)-c(v)|≥2；

(2)对任意的u,v∈V(G)，若d(u,v)=2，则|c(u)-c(v)|≥1.

当所有标号都小于等于k时,则称图G有一个k-L(2,1)-标号.使得图G有一个k-L(2,1)-标号的最小的正整数k称为图G的L(2,1)-标号数,记为λ(G).

定义2G=(V,E)和H=(W,F)的Cartesian积G□H定义如下:

V(G□H)=V×W且E(G□H)={{(u,x),(v,y)}:u=v且(x,y)∈F，或者x=y且(u,v)∈E}，其中E1={{(u,x),(u,y)}:u=v且(x,y)∈F}，E2={{(u,x),(v,y)}:x=y且(u,v)∈E}.

定义3E1中的每一条边用路Pk1替换,E2中的每一条边用路Pk2替换,得到的图称为Cartesian积G□H的局部边-不同长路的替换图,记为……