擬Mobius梯子的L(1，1，1)-標號

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

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

1 基本概念

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

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

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

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

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

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

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

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

本節將探究擬Mobius梯子的L(1，1，1)-標號.首先給出一個下界.

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

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

接下來我們對n≥3進行討論.

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

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

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

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

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

定理 2當n=4時，λ(M(4，k))≤7.

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

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

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

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

定理 3當n=5、6時，λ(M(n，k))=5.

證明：下界由引理1給出，則只需給出一個跨度5的標號.

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

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

定理 4當n=7、8時，λ(M(n，k))≤6.

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

定理 5當n≥9時，λ(M(n，k))=5.

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

當n≥9時，M(n，k)的標號可分別在n=5、6、11、12的上述標號基礎上，每小節以及扭結邊上增加四個相鄰標號循環獲得.