吳鈺莉，蔡 雨，陸靈杰，趙浩杰，劉文政，呂大梅

(南通大學(xué) 理學(xué)院，江蘇 南通 226007)

1 基本概念

圖著色問題是圖論的關(guān)鍵問題之一，頻率分配問題轉(zhuǎn)變成圖標(biāo)號問題，是圖著色問題的一個(gè)重要推廣之一.在1992年，Griggs跟Yeh一起提出了圖的L(2，1)-標(biāo)號這個(gè)問題[1]，即距離2標(biāo)號問題.對于距離2標(biāo)號而言，已有大量的圖類，像Cartesian積圖、擬梯子、擬Mobius梯子的L(2，1)-標(biāo)號數(shù)等已研究[2-5].有時(shí)頻率分配問題需要距離3的限制條件，這也就有了距離3標(biāo)號問題[7-9].本文將進(jìn)一步探討擬Mobius 梯子的L(1，1，1)-標(biāo)號.

定義 1(L(1，1，1)-標(biāo)號)圖G的一個(gè)L(1，1，1)-標(biāo)號是從頂點(diǎn)集V(G)到非負(fù)整數(shù)集的一個(gè)映射f，且當(dāng)d(u，v)=1，2，3時(shí)，均有|f(u)-f(v)|≥1；其中u，v是圖G的頂點(diǎn).不妨設(shè)0為最小標(biāo)號，則圖G的L(1，1，1)-標(biāo)號數(shù)λ1，1，1(G)是圖G的所有L(1，1，1)-標(biāo)號中的最大跨度f(v)的最小數(shù).L(1，1，1)-標(biāo)號主要問題之一就是要找出圖G的L(1，1，1)-標(biāo)號數(shù)λ1，1，1(G).為表達(dá)方便，本文中λ1，1，1(G)簡記為λ(G).

定義 2 (梯子)路P2與另一條頂點(diǎn)數(shù)大于3的路Pn的Cartesian積圖P2□Pn，稱為梯子.

定義 3(擬梯子)梯子行上的每一條邊用路Pk1替換，列中的每一條邊不變，得到的局部邊-路替換圖稱為擬梯子.

定義 4(擬梯子的等價(jià)定義)設(shè)一個(gè)2行n列的矩陣A2×n，其中的每個(gè)元aij(i=1，2，j=1，2，…，n)看作為點(diǎn)，將第一行a11，a12…a1n依次連接，同樣將第二行a21，a22…a2n依次連接，同時(shí)將a11與a21連接，a1n與a2n連接，得到一個(gè)圈C2n.再將k個(gè)由這樣的矩陣A2×n按此方式得到的圈C2n按如下方式組合：前一個(gè)圈C2n的末位a1n與a2n和后一個(gè)圈C2n的首位a11與a21，點(diǎn)點(diǎn)重疊，對應(yīng)的邊重疊，這樣形成的圖稱為擬梯子，記作P(n，k)(其中n表示每個(gè)矩陣A2×n的列數(shù)，k表示組合成擬梯子圖的圈C2n的個(gè)數(shù)).為表達(dá)方便，擬梯子P(n，k)中的第一個(gè)圈C2n稱為擬梯子的第一節(jié)，后面的依次為擬梯子的第2，3，…，k節(jié).

定義 5(擬Mobius 梯子)由擬梯子第一行的第一個(gè)頂點(diǎn)與第二行的最后一個(gè)頂點(diǎn)用n個(gè)頂點(diǎn)的路相連，以及第二行的第一個(gè)頂點(diǎn)與第一行的最后一個(gè)頂點(diǎn)用n個(gè)頂點(diǎn)的路相連所得的圖，稱之為擬Mobius 梯子，記為M(n，k).其中擬Mobius梯子M(n，k)中去掉扭接部分即為擬梯子P(n，k)，擬Mobius梯子M(n，k)P(n，k)多了扭接部分的兩條路，稱這兩條為擬Mobius梯子的扭結(jié)路.

當(dāng)n=2時(shí)，M(n，k)則為Mobius梯子.接下來對擬Mobius梯子的未扭結(jié)部分和增加的兩扭結(jié)路部分分別研究，從而給出n≥3時(shí)擬Mobius梯子的L(1，1，1)-標(biāo)號數(shù)的精確值或界.

2 擬Mobius梯子的L(1，1，1)-標(biāo)號

本節(jié)將探究擬Mobius梯子的L(1，1，1)-標(biāo)號.首先給出一個(gè)下界.

引理 1當(dāng)n≥3且k≥1時(shí)，有λ(M(n，k))≥2Δ-1=5.

證明：當(dāng)n≥3且k≥1時(shí)，由于每個(gè)圖都有兩個(gè)最大度為Δ的頂點(diǎn)相鄰，從而有λ(M(n，k))≥2Δ-1=5.

接下來我們對n≥3進(jìn)行討論.

定理 1當(dāng)n=3時(shí)，對k=1，有λ(M(3，k))=7；對k=2，有λ(M(3，k))=11；對k≥3，有λ(M(3，k))≤7.

證明：當(dāng)k=1時(shí)，M(3，1)是距離3的圖，又其頂點(diǎn)數(shù)為8，則有λ(M(3，1))≥7.下只需給出一個(gè)跨度7的標(biāo)號.M(3，1)中未扭結(jié)部分小節(jié)的標(biāo)號第一行為 0 2 3、第二行為1 5 6，增加的兩條扭結(jié)路標(biāo)號分別為：3 4 1與6 7 0.因此λ(M(3，1))=7.

當(dāng)k=2時(shí)，M(3，2)是距離3的圖，又其頂點(diǎn)數(shù)為12，則有λ(M(3，2))≥11.下只需給出一個(gè)跨度11的標(biāo)號.M(3，2)中未扭結(jié)部分第一小節(jié)的標(biāo)號第一行為 0 2 3、第二行為17 8，第一小節(jié)的標(biāo)號第一行為 3 4 5、第二行為8 9 10，增加的兩條扭結(jié)路標(biāo)號分別為：5 6 1與10 11 0.因此λ(M(3，2))=11.

當(dāng)k≥3時(shí)，只需給出一個(gè)跨度7的標(biāo)號.對k≡1mod 2，M(3，k)，中未扭結(jié)部分每兩小節(jié)的標(biāo)號按上面M(3，1)的標(biāo)號重復(fù)：即第一行按 0 2 3 4 1、第二行按1 5 6 7 0形式重復(fù)，最后一小節(jié)和扭結(jié)邊標(biāo)號就用上面M(3，1)的標(biāo)號，則給出k≡1mod2時(shí)M(3，k)時(shí)的跨度7標(biāo)號.因此當(dāng)k≡1mod2時(shí)，λ(M(3，k))≤7.

當(dāng)k≥3時(shí)，對k≡0 mod 2，M(3，k)，中未扭結(jié)部分前三小節(jié)的標(biāo)號如下：第一行為 0 2 3 4 5 6 0、第二行為1 5 6 7 2 3 1，接下來的未扭結(jié)部分每兩小節(jié)的標(biāo)號按上面M(3，1)的標(biāo)號重復(fù)，最后一小節(jié)和扭結(jié)邊標(biāo)號就用上面M(3，1)的標(biāo)號，則也給出k≡0 mod 2時(shí)M(4，k)的跨度7標(biāo)號.因此當(dāng)k≡0 mod 2時(shí)，λ(M(3，k))≤7.

定理 2當(dāng)n=4時(shí)，λ(M(4，k))≤7.

證明：只需給出一個(gè)跨度7的標(biāo)號.當(dāng)k=1時(shí)，M(4，1)中未扭結(jié)部分小節(jié)的標(biāo)號第一行為 0 23 6、第二行為1 32 7，增加的兩條扭結(jié)路標(biāo)號分別為：6 45 1與7 54 0.即給出M(4，1)的一個(gè)跨度7的標(biāo)號.因此λ(M(4，1))≤7.

當(dāng)k=2時(shí)，M(4，2)中未扭結(jié)部分第一小節(jié)的標(biāo)號第一行為 0 12 3、第二行為4 56 7，第二小節(jié)的標(biāo)號第一行為3 40 1、第二行為7 04 5，增加的兩條扭結(jié)路標(biāo)號分別為：1 23 4與5 67 0.即給出M(4，2)的一個(gè)跨度7的標(biāo)號.因此λ(M(4，2))≤7.

當(dāng)k≥3時(shí)，對k≡1mod2，M(4，k)，中未扭結(jié)部分每兩小節(jié)的標(biāo)號按上面M(4，1)的標(biāo)號重復(fù)：即第一行按 0 23 6 45 1、第二行按1 32 7 54 0形式重復(fù)，最后一小節(jié)和扭結(jié)邊標(biāo)號就用上面M(4，1)的標(biāo)號，則當(dāng)k≡1mod2時(shí)，λ(M(4，k))≤7.

當(dāng)k≥3時(shí)，對k≡0mod2，M(4，k)，中未扭結(jié)部分每兩小節(jié)的標(biāo)號按如下形式重復(fù)：第一行按 0 15 4 23 0、第二行按4 51 0 32 4形式重復(fù)，最后兩小節(jié)小節(jié)和扭結(jié)邊標(biāo)號就用上面M(4，2)的標(biāo)號.因此當(dāng)k≡0mod2時(shí)，λ(M(4，k))≤7.

定理 3當(dāng)n=5、6時(shí)，λ(M(n，k))=5.

證明：下界由引理1給出，則只需給出一個(gè)跨度5的標(biāo)號.

當(dāng)n=5時(shí)，M(5，k)中未扭結(jié)部分每小節(jié)的標(biāo)號第一行按 0 123 0形式重復(fù)、第二行按 5 214 5形式重復(fù)，擬梯子基礎(chǔ)上增加的兩條扭結(jié)路標(biāo)號分別為：0 123 5與5 214 0.即給出M(5，k)的一個(gè)跨度5的標(biāo)號.因此λ(M(5，k))=5.

當(dāng)n=6時(shí)，M(6，k)中未扭結(jié)部分每小節(jié)的標(biāo)號第一行按 0 1234 0形式重復(fù)、第二行按5 2143 5形式重復(fù)，擬梯子基礎(chǔ)上增加的兩條扭結(jié)路標(biāo)號分別為：0 1234 5與5 2143 0.即給出M(6，k)的一個(gè)跨度5的標(biāo)號.因此λ(M(6，k))=5.

定理 4當(dāng)n=7、8時(shí)，λ(M(n，k))≤6.

證明：只需給出一個(gè)跨度6的標(biāo)號.當(dāng)n=7時(shí)，M(7，k)中未扭結(jié)部分每小節(jié)的標(biāo)號第一行按0 12534 0形式重復(fù)、第二行按5 20143 5形式重復(fù)，擬梯子基礎(chǔ)上增加的兩條扭結(jié)路標(biāo)號分別為：0 12634 5與5 21643 0.即給出M(7，k)的一個(gè)跨度6的標(biāo)號.因此，λ(M(7，k))≤6.當(dāng)n=8時(shí)，M(8，k)中未扭結(jié)部分每小節(jié)的標(biāo)號第一行按 0 125634 0形式重復(fù)、第二行按5 206143 5形式重復(fù)，擬梯子基礎(chǔ)上增加的兩條扭結(jié)路標(biāo)號分別為：0 125634 5與5 210643 0.即給出M(8，k)的一個(gè)跨度6的標(biāo)號.因此，λ(M(8，k))≤6.

定理 5當(dāng)n≥9時(shí)，λ(M(n，k))=5.

證明：首先下界由引理1給出，則只需給出一個(gè)跨度5的標(biāo)號.當(dāng)n=11時(shí)，M(11，k)中未扭結(jié)部分每小節(jié)的標(biāo)號第一行按 0 1234051234 0形式重復(fù)、第二行按5 2143052143 5形式重復(fù)，擬梯子基礎(chǔ)上增加的兩條扭結(jié)路標(biāo)號分別為：0 1234051234 5與5 2143052143 0.即給出M(11，k)的一個(gè)跨度5的標(biāo)號.因此，λ(M(11，k))=5.當(dāng)n=12時(shí)，M(12，k)中未扭結(jié)部分每小節(jié)的標(biāo)號第一行按 0 1230125324 0形式重復(fù)、第二行按 5 2145210423 5形式重復(fù)，擬梯子基礎(chǔ)上增加的兩條扭結(jié)路標(biāo)號分別為：0 1230125324 5與5 2145210423 0.即給出M(12，k)的一個(gè)跨度5的標(biāo)號.因此，λ(M(12，k))=5.

當(dāng)n≥9時(shí)，M(n，k)的標(biāo)號可分別在n=5、6、11、12的上述標(biāo)號基礎(chǔ)上，每小節(jié)以及扭結(jié)邊上增加四個(gè)相鄰標(biāo)號循環(huán)獲得.