吴钰莉，蔡 雨，陆灵杰，赵浩杰，刘文政，吕大梅

(南通大学 理学院，江苏 南通 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称……