拟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的上述标号基础上，每小节以及扭结边上增加四个相邻标号循环获得.