一类积图的局部边路替换图的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的局部边-不同长路的替换图,记为(G□H)k1,k2.原来图G□H的顶点称为(G□H)k1,k2的节点.

本文主要研究(Pm□Pn)3,k的L(2,1)-标号.为了方便表示，我们在研究(Pm□Pn)3,k时,用坐标标记顶点.Pm的顶点记为0,1，…，m-1，Pn的顶点记为0,1，…，n-1，Pm□Pn的顶点为(i,j)(i=0,1，…，m-1，j=0,1，…，n-1)，称之为第i行j列的顶点.(Pm□Pn)3,k中i行上(i,j)和(i,j+1)之间的边插入的点从(i,j)后依次记为(i,0.1)，(i,0.2)，…，(i,0.(k-2))，(Pm□Pn)3,k中j列上(i,j)和(i+1,j)之间的边插入的点记为(i.5,j).

2 (Pm□Pn)3,k的L(2,1)-标号

本节中,我们研究路路的积图的局部边路替换图(Pm□Pn)3,k的L(2,1)-标号. 为了方便表述,用矩阵来表示(Pm□Pn)3,k上一循环段的标号.

引理1[16]设G是最大度为Δ≥2的图,λ(G)≥Δ(G)+1.

2.1 m=2

当n=2且k≥3时，(P2□Pn)3,k即为顶点数大于8偶圈C2k+2.又λ(C2k+2)=4.从而当n=2且k≥3时，λ((P2□Pn)3,k)=4.本节接下来的讨论中，m=2且n≥3.

定理1当n=3时,λ((P2□Pn)3，3)=4；当n≥4时,λ((P2□Pn)3，3)=5.

证明当n=3时, 由引理1,有λ((P2□Pn)3，3)≥4.又由矩阵(1),则我们可以给出(P2□Pn)3,3的跨度为4的L(2,1)-标号.从而当n=3时,λ((P2□Pn)3，3)=4.

当n≥4时,同样由引理1,有λ((P2□Pn)3，3)≥4.若最大标号为4，则Δ=3的点只能标0或4.从而有(0,1),(0,2),(1,1)和(1,2)只能标0或4，则(0.5,1)和(0,1.5)全标2,和标号定义矛盾,故λ((P2□Pn)3，3)>4.其次,由矩阵A2给出一个循环段,则我们可以给出(P2□Pn)3,3的跨度为5的L(2,1)-标号.因此,λ((P2□Pn)3，3)≤5.综上得,λ((P2□Pn)3，3)=5.这里

定理2当n=3,4时,λ((P2□Pn)3，4)=4；当n≥5时,λ((P2□Pn)3，4)=5.

证明当n=3,4时,同样由引理1,下界为4.又由矩阵(3)，则我们可以给出n=4时(P2□Pn)3,4的跨度为4的L(2,1)-标号.从而当n=4时,λ((P2□Pn)3，4)=4.从而而n=3时的图为n=4时的子图, 故当n=3时，也有λ((P2□Pn)3，4)=4.

当n≥5时,由引理1,下界为4.若最大标号为4，则又Δ=3的点只能标0或4.从而(0,1),(0,2),(0,3),(1,1),(1,2)和(1,3)只能标0或4，则(0.5,1),(0.5,2)和(0.5,3)全标2,不妨设(0,1)的标号为0，则(0,2),(0,3)标号必只能分别4,0，则(0,1)与(0,2)之间的替换路只能标为0314，而(0,2)与(0,3)之间的路也只能标为4130，则不能同时标定,故λ((P2□Pn)3，4)>4.其次,又由矩阵A4给出了一个循环段的标号,则我们可以给出(P2□Pn)3,4的跨度为5的L(2,1)-标号.因此,λ((P2□Pn)3，4)≤5.综上得,λ((P2□Pn)3，4)=5. 这里

定理3当k=5且n≥3时,λ((P2□Pn)3，5)=4.

证明首先,当k=5且n≥3时,由引理1,有λ((P2□Pn)3，5)≥4.不妨设最大标号为4，由矩阵(5)给出了一个循环段的标号,则我们可以给出(P2□Pn)3,5的跨度为4的L(2,1)-标号.综上,λ((P2□Pn)3，5)=4.

定理4当n=3时,λ((P2□Pn)3，6)=4；当n≥4时,λ((P2□Pn)3，6)=5.

证明当n=3时,同样由引理1,下界为4.又由A6，则我们可以给出(P2□Pn)3，6的跨度为4的L(2,1)-标号.从而n=3时,λ((P2□Pn)3，6)=4.

当n≥4时,由引理1,有λ((P2□Pn)3，6)≥4.若最大标号为4，则Δ=3的点只能标0或4.从而(0,1)， (0,2)， (0,3)， (1,1)， (1,2)和(1,3)只能标0或4，则(0.5,1)、(0.5,2)和(0.5,3)全标2.不妨设(0,1)的标号为0，则(0,2)，(0,3)标号必只能分别4,0，则(0,1)与(0,2)之间的替换路只能标为041304，而(0,2)与(0,3)之间的路也只能标为403140，则不能同时标定,故λ((P2□Pn)3，6)>4.其次,又由A7给出了一个循环段的标号,则我们可以给出(P2□Pn)3,6的跨度为5的L(2,1)-标号.因此,λ((P2□Pn)3，6)≤5.综上得,λ((P2□Pn)3，6)=5.这里

定理5当k≥7且n≥3时,λ((P2□Pn)3,k)=4.

证明 首先,当k≥7且n≥3时,由引理1,有λ((P2□Pn)3,k)≥4.由矩阵(8-11)给出了k=7,8,9,10对应图的一个循环段的标号,则我们可以给出k=7,8,9,10时(P2□Pn)3,k的跨度为4的L(2,1)-标号.综上得,当k=7,8,9,10时，λ((P2□Pn)3,k)=4.这里

当k≥11时,只要分别在k=8、k=9、k=10的标号基础上，每条替换路上插入[0,4]中的三个标号的可循环小节，就可分别得k=2mod3，k=0mod3，k=1mod3的L(2,1)-标号.从而当k≥11时, 也有λ((P2□Pn)3，k)=4.

2.2 m=3

当n=2且k≥3时，(P3□Pn)3,k的最大度为3，则此时标号数的下界为4.当n=2且k=3时，(P3□P2)3,k等同于2.1小节中的(P2□P3)3,k，从而由定理1，λ((P3□P2)3,3)=4.当n=2且k=6时，矩阵(12)给出了一个跨度为4的L(2,1)-标号，从而λ((P3□Pn)3,k=4；当n=2,m=3,k≥4且k≠6时，由于m=3时的图是m=4的子图，则由下一小节n=2、m=4相应k值的标号，有λ((P3□Pn)3,k=4.在本节接下来的讨论中，m=3且n≥3.这里

定理6当3≤n≤4时,λ((P3□Pn)3，3)=5；当n≥5时,λ((P3□Pn)3，3)=6.

证明当3≤n≤4时,由引理1,下界均为5.又由矩阵(13),则我们可以给出n=4时(P3□Pn)3,3的跨度为5的L(2,1)-标号，从而当k=3且n=4时,λ((P3□Pn)3，3)=5.由n=3时的图是n=4的子图，从而当k=3且n=3时,λ((P3□Pn)3，3)=5.

当n≥5时,由引理1,有λ((P3□Pn)3，3)≥5.若最大标号为5，则Δ=4的点只能标0或5.不妨设(0,0)=0，(1,0)=5.则有(0,1)=5，(1,1)=0.必有(0.5,0)=3，(0,0.1)=3，无法取得标号,故λ((P3□Pn)3，3)>5.又以矩阵A14(14)向右循环,则我们可以给出(P3□Pn)3,3的跨度为6的L(2,1)-标号.因此,λ((P3□Pn)5，3)≤6.综上,λ((P3□Pn)3，3)=6.

定理7当k≥4且n≥3时,λ((P3□Pn)3,k)=5.

证明首先,当k≥4且n≥3时,由引理1,有λ((P3□Pn)3,k)≥5.又以矩阵(15-18)为循环段向右循环,则我们可以给出k=4,5,6,7时(P3□Pn)3,k的跨度为5的L(2,1)-标号，因此,λ((P3□Pn)3,k)≤5.综上得,k=4,5,6,7时，λ((P3□Pn)3,k)=5.这里

当k≥8且n≥3时,分别在k=5，k=6，k=7的标号基础上，每条替换路上可插入[0,5]中的三个标号的可循环小节，则可分别得k=2mod3，k=0mod3，k=1mod3的L(2,1)-标号.从而有当k≥8时,λ((P3□Pn)3，k)=5.

2.3 m≥4

同2.2小节，当n=2,m≥4且k≥3时，(Pm□Pn)3,k的最大度也为3，故标号数的下界为4.当n=2,m≥4且k=3时，(Pm□P2)3,k等同于2.1小节中的(P2□Pm)3,k，则由定理1，λ((Pm□P2)3,3)=5.当n=2，m=4,k≥4且k≠6时，下矩阵(19-21)中分别给出了k=4,5,9时跨度为4的一段循环标号，k≥7时可在k=4,5,9时的标号基础上在各替换路上加上三标号的循环可得，则此时，λ((Pm□Pn)3,k=4. 这里

当n=2，m=4且k=6时，若最大标号为4，由于度为4的节点须标0或4，则第2行和第3行上边的替换路的标号必为041304和403140，则第0行和第3行上边的替换路无法用[0,4]中的整数标号标定，从而λ((Pm□Pn)3,k≥5；又跨度为5的L(2,1)-标号可由接下来的n=2,m≥5且k=6时的标号中截取而得，从而λ((Pm□Pn)3,k=5.

当n=2，m≥5且k≥4时，若最大标号为4，由于度为4的节点须标0或4，则(1.5,1)与(2.5,1)均须标为2，矛盾，从而λ((Pm□Pn)3,k≥5；又从矩阵A22-A25中分别给出了k=4,5,6时跨度为5的一段的循环标号，k≥7时可在k=4,5,6时的标号基础上在各替换路上加上三个可循环的标号的循环可得，从而当n=2，m≥4且k≥5时，λ((Pm□Pn)3,k=5.在本节接下来的讨论中，m≥4且n≥3.这里

对(Pm□Pn)3,k，m=3时的图是m≥4时的图的子图，故m≥4时的标号数也以m=3时的标号数为下界.又m=3，n≥3且k≥5时的标号可向下循环，则我们可以给出m≥4，n≥3且k≥5的(Pm□Pn)3,k的L(2,1)-标号；同样，m=3，n≥5且k=3时的标号也可向下循环，则得如下结论.

定理8设m≥4.当n≥3且k≥5时，有λ((Pm□Pn)3，k)=5； 当n≥5且k=3时，有λ((Pm□Pn)3，3)=6.

当m≥4，n=3且k=3时,由m与n的对称性及定理6中n≥4的结论，可得如下结果.

定理9设m≥4，n=3且k=3.则当m=4时，有λ((Pm□Pn)3，3)=5；当m≥4时，有λ((Pm□Pn)3，3)=6.

对k=3且m≥4，n=4，我们有如下结果.

定理10当m≥5，n=4且k=3时,λ((Pm□P4)3，3)=6；当m=4，n=4时,λ((P4□P4)3，3)=5.

证明当k=3时，m≥5，n=4时的图同构于m=4，n≥5的图,由m与n的对称性及定理2.3.2的结论，可得λ((Pm□P4)3，3)=6.当m=4，n=4时,由引理1,有λ((P4□P4)3，3)≥5.由矩阵2.3.4,则我们可以给出(Pm□P4)3，3的跨度为5的L(2,1)-标号.综上得,λ((P4□P4)3，3)=5.

对m≥4，n≥3且k=4，有如下结果.

定理11当m≥5，n≥5时,λ((Pm□P4)3，4)=6；当m=4,n≥5，或m≥4,3≤n≤4时,λ((P4□P4)3，4)=5.

证明当m≥4，n≥3且k=4时，由引理1，下界为5.

对m=4，n≥5，及m≥4，3≤n≤4时, 分别以矩阵(26-27)为循环段,则我们可以给出这两种种情形下跨度为5的L(2,1)-标号.综上得,λ((P4□P4)3，4)=5.而对m≥5，n≥5， 若最大标号为5，由于度为5的节点须标0或5，则(1.5,1)与(2.5,1),及(1.5,2)与(2.5,2)标号只能为2或3，则第一行中的替换路标号为0415或5140，矛盾，从而λ((Pm□Pn)3,4≥6；又,由矩阵A28，则我们可以给出此种情形下跨度为6的L(2,1)-标号.综上得,λ((Pm□P4)3，4)=6.这里