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

(1. 南通師范高等?？茖W(xué)校， 南通，226007;2. 南通大學(xué)理學(xué)院，南通，226007)

1 引言

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

定義1圖G的一個(gè)L(2,1)-標(biāo)號(hào)是一個(gè)滿足下兩個(gè)條件的映射c:V(G)→(0,1,2，…，k)，

(1)對(duì)任意的u,v∈V(G)，若d(u,v)=1，則|c(u)-c(v)|≥2；

(2)對(duì)任意的u,v∈V(G)，若d(u,v)=2，則|c(u)-c(v)|≥1.

當(dāng)所有標(biāo)號(hào)都小于等于k時(shí),則稱圖G有一個(gè)k-L(2,1)-標(biāo)號(hào).使得圖G有一個(gè)k-L(2,1)-標(biāo)號(hào)的最小的正整數(shù)k稱為圖G的L(2,1)-標(biāo)號(hào)數(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的頂點(diǎn)稱為(G□H)k1,k2的節(jié)點(diǎn).

本文主要研究(Pm□Pn)3,k的L(2,1)-標(biāo)號(hào).為了方便表示，我們?cè)谘芯?Pm□Pn)3,k時(shí),用坐標(biāo)標(biāo)記頂點(diǎn).Pm的頂點(diǎn)記為0,1，…，m-1，Pn的頂點(diǎn)記為0,1，…，n-1，Pm□Pn的頂點(diǎn)為(i,j)(i=0,1，…，m-1，j=0,1，…，n-1)，稱之為第i行j列的頂點(diǎn).(Pm□Pn)3,k中i行上(i,j)和(i,j+1)之間的邊插入的點(diǎn)從(i,j)后依次記為(i,0.1)，(i,0.2)，…，(i,0.(k-2))，(Pm□Pn)3,k中j列上(i,j)和(i+1,j)之間的邊插入的點(diǎn)記為(i.5,j).

2 (Pm□Pn)3,k的L(2,1)-標(biāo)號(hào)

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

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

2.1 m=2

當(dāng)n=2且k≥3時(shí)，(P2□Pn)3,k即為頂點(diǎn)數(shù)大于8偶圈C2k+2.又λ(C2k+2)=4.從而當(dāng)n=2且k≥3時(shí)，λ((P2□Pn)3,k)=4.本節(jié)接下來的討論中，m=2且n≥3.

定理1當(dāng)n=3時(shí),λ((P2□Pn)3，3)=4；當(dāng)n≥4時(shí),λ((P2□Pn)3，3)=5.

證明當(dāng)n=3時(shí), 由引理1,有λ((P2□Pn)3，3)≥4.又由矩陣(1),則我們可以給出(P2□Pn)3,3的跨度為4的L(2,1)-標(biāo)號(hào).從而當(dāng)n=3時(shí),λ((P2□Pn)3，3)=4.

當(dāng)n≥4時(shí),同樣由引理1,有λ((P2□Pn)3，3)≥4.若最大標(biāo)號(hào)為4，則Δ=3的點(diǎn)只能標(biāo)0或4.從而有(0,1),(0,2),(1,1)和(1,2)只能標(biāo)0或4，則(0.5,1)和(0,1.5)全標(biāo)2,和標(biāo)號(hào)定義矛盾,故λ((P2□Pn)3，3)>4.其次,由矩陣A2給出一個(gè)循環(huán)段,則我們可以給出(P2□Pn)3,3的跨度為5的L(2,1)-標(biāo)號(hào).因此,λ((P2□Pn)3，3)≤5.綜上得,λ((P2□Pn)3，3)=5.這里

定理2當(dāng)n=3,4時(shí),λ((P2□Pn)3，4)=4；當(dāng)n≥5時(shí),λ((P2□Pn)3，4)=5.

證明當(dāng)n=3,4時(shí),同樣由引理1,下界為4.又由矩陣(3)，則我們可以給出n=4時(shí)(P2□Pn)3,4的跨度為4的L(2,1)-標(biāo)號(hào).從而當(dāng)n=4時(shí),λ((P2□Pn)3，4)=4.從而而n=3時(shí)的圖為n=4時(shí)的子圖, 故當(dāng)n=3時(shí)，也有λ((P2□Pn)3，4)=4.

當(dāng)n≥5時(shí),由引理1,下界為4.若最大標(biāo)號(hào)為4，則又Δ=3的點(diǎn)只能標(biāo)0或4.從而(0,1),(0,2),(0,3),(1,1),(1,2)和(1,3)只能標(biāo)0或4，則(0.5,1),(0.5,2)和(0.5,3)全標(biāo)2,不妨設(shè)(0,1)的標(biāo)號(hào)為0，則(0,2),(0,3)標(biāo)號(hào)必只能分別4,0，則(0,1)與(0,2)之間的替換路只能標(biāo)為0314，而(0,2)與(0,3)之間的路也只能標(biāo)為4130，則不能同時(shí)標(biāo)定,故λ((P2□Pn)3，4)>4.其次,又由矩陣A4給出了一個(gè)循環(huán)段的標(biāo)號(hào),則我們可以給出(P2□Pn)3,4的跨度為5的L(2,1)-標(biāo)號(hào).因此,λ((P2□Pn)3，4)≤5.綜上得,λ((P2□Pn)3，4)=5. 這里

定理3當(dāng)k=5且n≥3時(shí),λ((P2□Pn)3，5)=4.

證明首先,當(dāng)k=5且n≥3時(shí),由引理1,有λ((P2□Pn)3，5)≥4.不妨設(shè)最大標(biāo)號(hào)為4，由矩陣(5)給出了一個(gè)循環(huán)段的標(biāo)號(hào),則我們可以給出(P2□Pn)3,5的跨度為4的L(2,1)-標(biāo)號(hào).綜上,λ((P2□Pn)3，5)=4.

定理4當(dāng)n=3時(shí),λ((P2□Pn)3，6)=4；當(dāng)n≥4時(shí),λ((P2□Pn)3，6)=5.

證明當(dāng)n=3時(shí),同樣由引理1,下界為4.又由A6，則我們可以給出(P2□Pn)3，6的跨度為4的L(2,1)-標(biāo)號(hào).從而n=3時(shí),λ((P2□Pn)3，6)=4.

當(dāng)n≥4時(shí),由引理1,有λ((P2□Pn)3，6)≥4.若最大標(biāo)號(hào)為4，則Δ=3的點(diǎn)只能標(biāo)0或4.從而(0,1)， (0,2)， (0,3)， (1,1)， (1,2)和(1,3)只能標(biāo)0或4，則(0.5,1)、(0.5,2)和(0.5,3)全標(biāo)2.不妨設(shè)(0,1)的標(biāo)號(hào)為0，則(0,2)，(0,3)標(biāo)號(hào)必只能分別4,0，則(0,1)與(0,2)之間的替換路只能標(biāo)為041304，而(0,2)與(0,3)之間的路也只能標(biāo)為403140，則不能同時(shí)標(biāo)定,故λ((P2□Pn)3，6)>4.其次,又由A7給出了一個(gè)循環(huán)段的標(biāo)號(hào),則我們可以給出(P2□Pn)3,6的跨度為5的L(2,1)-標(biāo)號(hào).因此,λ((P2□Pn)3，6)≤5.綜上得,λ((P2□Pn)3，6)=5.這里

定理5當(dāng)k≥7且n≥3時(shí),λ((P2□Pn)3,k)=4.

證明 首先,當(dāng)k≥7且n≥3時(shí),由引理1,有λ((P2□Pn)3,k)≥4.由矩陣(8-11)給出了k=7,8,9,10對(duì)應(yīng)圖的一個(gè)循環(huán)段的標(biāo)號(hào),則我們可以給出k=7,8,9,10時(shí)(P2□Pn)3,k的跨度為4的L(2,1)-標(biāo)號(hào).綜上得,當(dāng)k=7,8,9,10時(shí)，λ((P2□Pn)3,k)=4.這里

當(dāng)k≥11時(shí),只要分別在k=8、k=9、k=10的標(biāo)號(hào)基礎(chǔ)上，每條替換路上插入[0,4]中的三個(gè)標(biāo)號(hào)的可循環(huán)小節(jié)，就可分別得k=2mod3，k=0mod3，k=1mod3的L(2,1)-標(biāo)號(hào).從而當(dāng)k≥11時(shí), 也有λ((P2□Pn)3，k)=4.

2.2 m=3

當(dāng)n=2且k≥3時(shí)，(P3□Pn)3,k的最大度為3，則此時(shí)標(biāo)號(hào)數(shù)的下界為4.當(dāng)n=2且k=3時(shí)，(P3□P2)3,k等同于2.1小節(jié)中的(P2□P3)3,k，從而由定理1，λ((P3□P2)3,3)=4.當(dāng)n=2且k=6時(shí)，矩陣(12)給出了一個(gè)跨度為4的L(2,1)-標(biāo)號(hào)，從而λ((P3□Pn)3,k=4；當(dāng)n=2,m=3,k≥4且k≠6時(shí)，由于m=3時(shí)的圖是m=4的子圖，則由下一小節(jié)n=2、m=4相應(yīng)k值的標(biāo)號(hào)，有λ((P3□Pn)3,k=4.在本節(jié)接下來的討論中，m=3且n≥3.這里

定理6當(dāng)3≤n≤4時(shí),λ((P3□Pn)3，3)=5；當(dāng)n≥5時(shí),λ((P3□Pn)3，3)=6.

證明當(dāng)3≤n≤4時(shí),由引理1,下界均為5.又由矩陣(13),則我們可以給出n=4時(shí)(P3□Pn)3,3的跨度為5的L(2,1)-標(biāo)號(hào)，從而當(dāng)k=3且n=4時(shí),λ((P3□Pn)3，3)=5.由n=3時(shí)的圖是n=4的子圖，從而當(dāng)k=3且n=3時(shí),λ((P3□Pn)3，3)=5.

當(dāng)n≥5時(shí),由引理1,有λ((P3□Pn)3，3)≥5.若最大標(biāo)號(hào)為5，則Δ=4的點(diǎn)只能標(biāo)0或5.不妨設(shè)(0,0)=0，(1,0)=5.則有(0,1)=5，(1,1)=0.必有(0.5,0)=3，(0,0.1)=3，無法取得標(biāo)號(hào),故λ((P3□Pn)3，3)>5.又以矩陣A14(14)向右循環(huán),則我們可以給出(P3□Pn)3,3的跨度為6的L(2,1)-標(biāo)號(hào).因此,λ((P3□Pn)5，3)≤6.綜上,λ((P3□Pn)3，3)=6.

定理7當(dāng)k≥4且n≥3時(shí),λ((P3□Pn)3,k)=5.

證明首先,當(dāng)k≥4且n≥3時(shí),由引理1,有λ((P3□Pn)3,k)≥5.又以矩陣(15-18)為循環(huán)段向右循環(huán),則我們可以給出k=4,5,6,7時(shí)(P3□Pn)3,k的跨度為5的L(2,1)-標(biāo)號(hào)，因此,λ((P3□Pn)3,k)≤5.綜上得,k=4,5,6,7時(shí)，λ((P3□Pn)3,k)=5.這里

當(dāng)k≥8且n≥3時(shí),分別在k=5，k=6，k=7的標(biāo)號(hào)基礎(chǔ)上，每條替換路上可插入[0,5]中的三個(gè)標(biāo)號(hào)的可循環(huán)小節(jié)，則可分別得k=2mod3，k=0mod3，k=1mod3的L(2,1)-標(biāo)號(hào).從而有當(dāng)k≥8時(shí),λ((P3□Pn)3，k)=5.

2.3 m≥4

同2.2小節(jié)，當(dāng)n=2,m≥4且k≥3時(shí)，(Pm□Pn)3,k的最大度也為3，故標(biāo)號(hào)數(shù)的下界為4.當(dāng)n=2,m≥4且k=3時(shí)，(Pm□P2)3,k等同于2.1小節(jié)中的(P2□Pm)3,k，則由定理1，λ((Pm□P2)3,3)=5.當(dāng)n=2，m=4,k≥4且k≠6時(shí)，下矩陣(19-21)中分別給出了k=4,5,9時(shí)跨度為4的一段循環(huán)標(biāo)號(hào)，k≥7時(shí)可在k=4,5,9時(shí)的標(biāo)號(hào)基礎(chǔ)上在各替換路上加上三標(biāo)號(hào)的循環(huán)可得，則此時(shí)，λ((Pm□Pn)3,k=4. 這里

當(dāng)n=2，m=4且k=6時(shí)，若最大標(biāo)號(hào)為4，由于度為4的節(jié)點(diǎn)須標(biāo)0或4，則第2行和第3行上邊的替換路的標(biāo)號(hào)必為041304和403140，則第0行和第3行上邊的替換路無法用[0,4]中的整數(shù)標(biāo)號(hào)標(biāo)定，從而λ((Pm□Pn)3,k≥5；又跨度為5的L(2,1)-標(biāo)號(hào)可由接下來的n=2,m≥5且k=6時(shí)的標(biāo)號(hào)中截取而得，從而λ((Pm□Pn)3,k=5.

當(dāng)n=2，m≥5且k≥4時(shí)，若最大標(biāo)號(hào)為4，由于度為4的節(jié)點(diǎn)須標(biāo)0或4，則(1.5,1)與(2.5,1)均須標(biāo)為2，矛盾，從而λ((Pm□Pn)3,k≥5；又從矩陣A22-A25中分別給出了k=4,5,6時(shí)跨度為5的一段的循環(huán)標(biāo)號(hào)，k≥7時(shí)可在k=4,5,6時(shí)的標(biāo)號(hào)基礎(chǔ)上在各替換路上加上三個(gè)可循環(huán)的標(biāo)號(hào)的循環(huán)可得，從而當(dāng)n=2，m≥4且k≥5時(shí)，λ((Pm□Pn)3,k=5.在本節(jié)接下來的討論中，m≥4且n≥3.這里

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

定理8設(shè)m≥4.當(dāng)n≥3且k≥5時(shí)，有λ((Pm□Pn)3，k)=5； 當(dāng)n≥5且k=3時(shí)，有λ((Pm□Pn)3，3)=6.

當(dāng)m≥4，n=3且k=3時(shí),由m與n的對(duì)稱性及定理6中n≥4的結(jié)論，可得如下結(jié)果.

定理9設(shè)m≥4，n=3且k=3.則當(dāng)m=4時(shí)，有λ((Pm□Pn)3，3)=5；當(dāng)m≥4時(shí)，有λ((Pm□Pn)3，3)=6.

對(duì)k=3且m≥4，n=4，我們有如下結(jié)果.

定理10當(dāng)m≥5，n=4且k=3時(shí),λ((Pm□P4)3，3)=6；當(dāng)m=4，n=4時(shí),λ((P4□P4)3，3)=5.

證明當(dāng)k=3時(shí)，m≥5，n=4時(shí)的圖同構(gòu)于m=4，n≥5的圖,由m與n的對(duì)稱性及定理2.3.2的結(jié)論，可得λ((Pm□P4)3，3)=6.當(dāng)m=4，n=4時(shí),由引理1,有λ((P4□P4)3，3)≥5.由矩陣2.3.4,則我們可以給出(Pm□P4)3，3的跨度為5的L(2,1)-標(biāo)號(hào).綜上得,λ((P4□P4)3，3)=5.

對(duì)m≥4，n≥3且k=4，有如下結(jié)果.

定理11當(dāng)m≥5，n≥5時(shí),λ((Pm□P4)3，4)=6；當(dāng)m=4,n≥5，或m≥4,3≤n≤4時(shí),λ((P4□P4)3，4)=5.

證明當(dāng)m≥4，n≥3且k=4時(shí)，由引理1，下界為5.

對(duì)m=4，n≥5，及m≥4，3≤n≤4時(shí), 分別以矩陣(26-27)為循環(huán)段,則我們可以給出這兩種種情形下跨度為5的L(2,1)-標(biāo)號(hào).綜上得,λ((P4□P4)3，4)=5.而對(duì)m≥5，n≥5， 若最大標(biāo)號(hào)為5，由于度為5的節(jié)點(diǎn)須標(biāo)0或5，則(1.5,1)與(2.5,1),及(1.5,2)與(2.5,2)標(biāo)號(hào)只能為2或3，則第一行中的替換路標(biāo)號(hào)為0415或5140，矛盾，從而λ((Pm□Pn)3,4≥6；又,由矩陣A28，則我們可以給出此種情形下跨度為6的L(2,1)-標(biāo)號(hào).綜上得,λ((Pm□P4)3，4)=6.這里