一類積圖的局部邊路替換圖的L(2,1)-

(1. 南通師范高等專科學校， 南通，226007;2. 南通大學理學院，南通，226007)

1 引言

圖的距離2標號是經(jīng)典點著色的一個自然推廣.它是在無線電通信波段分配的促動下的自然產(chǎn)物，是無線電通信波段分配問題的圖論模式，它的研究成果對波段分配問題起著推進作用，受到多個領域學者們的極大關注.在圖的距離2標號中，要求相鄰頂點的標號差至少為2，兩個距離為2的頂點的標號相差至少為1. 距離2標號的相關研究可參見綜述[13-15].其中圖的關聯(lián)圖的距離2 標號問題，也即圖的(d,1)-全標號問題.1995年，Whittlesty，Georges 和Mauro[1]首先研究了圖G的關聯(lián)圖的L(2,1)-標號.2002年，Havet和Yu[2-3]稱圖G的剖分圖(圖的剖分圖即在圖的每條邊上再插入一個頂點所得的圖)的L(2,1)-標號為圖G的(2,1)-全標號，同時將之推廣得(d,1)-全標號概念.Havet和Yu 在研究了(d,1)-全標號數(shù)的一般規(guī)律.圖的(d,1)-全標號問題即研究圖的關聯(lián)圖的距離2 標號問題.圖的關聯(lián)圖可看成圖的邊-路P3替換圖.近幾年，關于邊-路替換圖的標號問題，已經(jīng)有了一些研究[2-12]. 本文進一步研究路路積圖的局部替換圖的L(2,1)-標號問題，并完全得到了該圖的L(2,1)-標號數(shù).

定義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)-標號的最小的正整數(shù)k稱為圖G的L(2,1)-標號數(shù),記為λ(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的節(jié)點.

本文主要研究(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)-標號

本節(jié)中,我們研究路路的積圖的局部邊路替換圖(Pm□Pn)3,k的L(2,1)-標號. 為了方便表述,用矩陣來表示(Pm□Pn)3,k上一循環(huán)段的標號.

引理1[16]設G是最大度為Δ≥2的圖,λ(G)≥Δ(G)+1.

2.1 m=2

當n=2且k≥3時，(P2□Pn)3,k即為頂點數(shù)大于8偶圈C2k+2.又λ(C2k+2)=4.從而當n=2且k≥3時，λ((P2□Pn)3,k)=4.本節(jié)接下來的討論中，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給出一個循環(huán)段,則我們可以給出(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給出了一個循環(huán)段的標號,則我們可以給出(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)給出了一個循環(huán)段的標號,則我們可以給出(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給出了一個循環(huán)段的標號,則我們可以給出(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對應圖的一個循環(huán)段的標號,則我們可以給出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]中的三個標號的可循環(huán)小節(jié)，就可分別得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，則此時標號數(shù)的下界為4.當n=2且k=3時，(P3□P2)3,k等同于2.1小節(jié)中的(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的子圖，則由下一小節(jié)n=2、m=4相應k值的標號，有λ((P3□Pn)3,k=4.在本節(jié)接下來的討論中，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)向右循環(huán),則我們可以給出(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)為循環(huán)段向右循環(huán),則我們可以給出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]中的三個標號的可循環(huán)小節(jié)，則可分別得k=2mod3，k=0mod3，k=1mod3的L(2,1)-標號.從而有當k≥8時,λ((P3□Pn)3，k)=5.

2.3 m≥4

同2.2小節(jié)，當n=2,m≥4且k≥3時，(Pm□Pn)3,k的最大度也為3，故標號數(shù)的下界為4.當n=2,m≥4且k=3時，(Pm□P2)3,k等同于2.1小節(jié)中的(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的一段循環(huán)標號，k≥7時可在k=4,5,9時的標號基礎上在各替換路上加上三標號的循環(huán)可得，則此時，λ((Pm□Pn)3,k=4. 這里

當n=2，m=4且k=6時，若最大標號為4，由于度為4的節(jié)點須標0或4，則第2行和第3行上邊的替換路的標號必為041304和403140，則第0行和第3行上邊的替換路無法用[0,4]中的整數(shù)標號標定，從而λ((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的節(jié)點須標0或4，則(1.5,1)與(2.5,1)均須標為2，矛盾，從而λ((Pm□Pn)3,k≥5；又從矩陣A22-A25中分別給出了k=4,5,6時跨度為5的一段的循環(huán)標號，k≥7時可在k=4,5,6時的標號基礎上在各替換路上加上三個可循環(huán)的標號的循環(huán)可得，從而當n=2，m≥4且k≥5時，λ((Pm□Pn)3,k=5.在本節(jié)接下來的討論中，m≥4且n≥3.這里

對(Pm□Pn)3,k，m=3時的圖是m≥4時的圖的子圖，故m≥4時的標號數(shù)也以m=3時的標號數(shù)為下界.又m=3，n≥3且k≥5時的標號可向下循環(huán)，則我們可以給出m≥4，n≥3且k≥5的(Pm□Pn)3,k的L(2,1)-標號；同樣，m=3，n≥5且k=3時的標號也可向下循環(huán)，則得如下結論.

定理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)為循環(huán)段,則我們可以給出這兩種種情形下跨度為5的L(2,1)-標號.綜上得,λ((P4□P4)3，4)=5.而對m≥5，n≥5， 若最大標號為5，由于度為5的節(jié)點須標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.這里