0 引言
本文中所涉及的都是有限、无向的简单图.$V(G)$和$E(G)$表示图$G$的点集合和边集合, $\Delta(G)$表示图$G$的最大度, $\delta (G)$表示图$G$的最小度, $P_n$是指长为$n-1$的路, $C_n $是指长为$n$的圈.
定义1[1] 设$G$是一个有限简单图(假设$G$不是空图), 令$d$是一个正整数.图$G$的$(d, 1)$-全标号是$V(G)\cup E(G)$到整数集合的一个映射$f$, 且满足
(1) 对任意$x, y\in V(G)$且$x$和$y$相邻, 有$\left| {f(x)-f(y)}\right|\ge 1$;
(2) 对任意$x=uv, y=vw$且$x, y\in E(G)$, 有$\left| {f(x)-f(y)}\right|\ge 1$;
(3) 对任意两个相关联的点$x$和边$y$, 有$\left| {f(x)-f(y)}\right|\ge d$.
$(k)-(d, 1)$-全标号是指在集合$\left\{ {0, 1, 2, \cdots, k}\right\}$中取值的$(d, 1)$-全标号.我们用图$G$中任意两个标号之间差的绝对值的最大值来表示图$G$的$(d, 1)$-全标号跨度, 即
|
$
\max \{\vert f(x)-f(y)\vert \vert x, y\in V(G)\cup E(G)\}.
$
|
在图$G$中所有的$(k)-(d, 1)$-全标号最小跨度(最小值$k)$为$(d, 1)$-全数$\lambda _d^T (G)$, 即
|
$
\lambda _d^T =\min\limits_f \max \{\vert f(x)-f(y)\vert \vert x,
y\in V(G)\cup E(G)\}.
$
|
定义2[2] 图$G$与$H$的字典式乘积记为$G\circ H$, 它的顶点集为$V(G)\times V(H)$, 且顶点$(u, v)$与$(u', v')$相邻当且仅当$uu'\in E(G)$, 或$u=u'$且$vv'\in E(H)$.
引理1[3] 若图$G$是一个有最大度$\Delta$的图, 则
(1) $\lambda _d (G)\ge \Delta (G)+d-1$;
(2) 若图$G$是$\Delta $-正则图, 则$\lambda _d (G)\ge \Delta(G)+d$;
(3) 若$d\geq\Delta (G)$, 则$\lambda _d (G)\ge \Delta (G)+d$;
(4) 若$\lambda _d (G)=\Delta (G)+d-1$, $f$是图$G$在标号集$\left\{ {0, 1, 2, \cdots, \Delta +d-1}\right\}$上的一个$(\Delta+d-1)-(d, 1)$-全标号, 则对于图$G$中的每一个最大度点$v$都有$f(v)=0$, 或者$f(v)=\Delta(G)+d-1$.
引理2[3] 对于任意的图$G$, $\lambda _d^T(G)\le \chi (G)+\chi '(G)+d-2$.
引理3[3] $\lambda _2^T (K_4)=6$, $\lambda_3^T (K_4)=7$, $\lambda _4^T (K_4)=9$, $\lambda _{3+i}^T (K_4)\le 7+2i$.
定理1[3] 若$d\geq n+1$, 则$\lambda_d^T (K_n)=2n+d-3$.
1 主要结果及证明
在以下证明中用$x_{ij} =(u_i, v_j)$来表示$G\circ H$中的点, 其中$u_i \in V(G), v_j \in V(H)$, 用$R(x)$表示与标号为$x$的顶点相关联的边可以取到的标号集合; 用$r(x)$表示与标号为$x$的顶点相邻的顶点可以取到的标号集合.
定理2 $P_2 \circ P_2 $是$K_4 $完全图, 且$d+3\le \lambda _d^T (P_2 \circ P_2)=\lambda _d^T (K_4)\le d+5$.当$d=1$时, $\lambda _d^T (P_2 \circ P_3)=d+3=4$; 当$2\le d\le 3$时, $ \lambda _d^T (P_2 \circ P_2)=d+4$; 当$d\ge 4$时, $ \lambda _d^T (P_2 \circ P_2)=d+5$.
证明 (1)当$d\geq n+1=5$时, 由引理1可知$\lambda _d^T (P_2 \circ P_2)=2n+d-3=d+5$.特别地, $d=4$时, 由引理3可知$\lambda _d^T (K_4)=9$, 故$d\geq4$时, $\lambda _d^T (P_2 \circ P_2)=d+5$.
(2) 当$2\leq d\leq 3$时, 由引理3可知$\lambda _2^T (K_4)=6$, $\lambda _3^T (K_4)=7$, 所以$\lambda _d^T (P_2 \circ P_2)=d+4$.
(3) 当$d=1$时, 令$f(x_{11})=0$, $f(x_{1{2}})={3}$, $f(x_{{2}1})={2}$, $f(x_{{22}})={4}$, $f(x_{11} x_{12})=4$, $f(x_{11} x_{2{1}})={1}$, $f(x_{11} x_{{2}2})={2}$, $f(x_{{21}}x_{{2}2})={3}_{, }f(x_{{2}1} x_{12})={0}$, $f(x_{1{2}} x_{{2}2})={1}$, 则可得到图$P_2 \circ P_2$的一种全标号方法.故$\lambda_d^T (P_2 \circ P_2)=d+3=4$.
定理3 对于图$P_2 \circ P_2 $我们有以下结论:
(1) 当$d=2$, $n\ge 4$时, $\lambda _d^T (P_2 \circ P_n)=\Delta+d$.
(2) 当$d\ge \Delta $时, 若$n=3$, 则$\lambda _d^T (P_2 \circ P_3)=\Delta +d+1$; 若$n\ge 4$, 则$\lambda _d^T (P_2 \circ P_n)=\Delta +d+2$.
证明 由字典式积的定义可得$P_2 \circ P_n $是$\Delta =n+2$, 其余度数均为$n+1$的简单图.
(1) 由引理1可得$\lambda _d^T (P_2 \circ P_n)\ge \Delta +d-1$.若图$P_2 \circ P_n $在$[0, \Delta +d-1]$上存在一个$(d, 1)$-全标号, 则由引理1可知:若$d(v)=\Delta $, 则有$f(v)=0$, 或$f(v)=\Delta +d-1$.在图$P_2 \circ P_n $中除去点$x_{11}, x_{1n}, x_{21}, x_{2n} $外, 其他点的度数均为$\Delta$.且存在一个子图为$K_4 $, 其中每个顶点度数均为$\Delta $, 而已知$f(v)=0$或$f(v)=\Delta+d+1$, 推出矛盾, 故$\lambda _d^T (P_2 \circ P_n)\ge \Delta +d$.
下面分$n$为偶数和奇数两种情况给出图$P_2 \circ P_n$的一种$(n+4)$-$(d, 1)$-全标号方法.
① $n$为偶数
当$j$为奇数时, 令$f(x_{1j} x_{1(j+1)})=n+4, $ $f(x_{{2}j}x_{{2}(j+1)})={0}$; 当$j$为偶数时, 令$f(x_{1j} x_{1(j+1)})=n+{3}$, $f(x_{{2}j} x_{{2}(j+1)})={1}$.其他边和顶点的标号如表 1所示.
表 1(Tab. 1)
表 1 当$n$为偶数时, $ {P_2\circ P_n }$的一种${(n+4)}- {(2, 1)}$-全标号方法
Tab. 1 $(n+4)-(2, 1)$-total labelling of $P_2 \circ P_n $, when $n$ is even
|
$x_{11} (0)$ |
$x_{12} (1)$ |
$\cdots $ |
$x_{1(n-1)} (0)$ |
$x_{1n} (1)$ |
| $x_{21} (n+3)$ |
2 |
3 |
$\cdots $ |
$n$ |
$n+1$ |
| $x_{22} (n+4)$ |
3 |
4 |
$\cdots $ |
$n+1$ |
$n+2$ |
| $\vdots $ |
$\vdots $ |
$\vdots $ |
|
$\vdots $ |
$\vdots $ |
| $x_{2(n-1)} (n+3)$ |
$n$ |
$n+1$ |
$\cdots $ |
$n-2$ |
$n-1$ |
| $x_{2n} (n+4)$ |
$n+1$ |
$n+2$ |
$\cdots $ |
$n-1$ |
$n$ |
|
表 1 当$n$为偶数时, $ {P_2\circ P_n }$的一种${(n+4)}- {(2, 1)}$-全标号方法
Tab. 1 $(n+4)-(2, 1)$-total labelling of $P_2 \circ P_n $, when $n$ is even
|
② $n$为奇数
对于$j\in [1, n{-1}]$, 当$j$为奇数时, 令$f(x_{1j} x_{1(j+1)})=n+{3}$, $f(x_{{2}j} x_{{2}(j+1)})={0}$; 当$j$为偶数时, 令$f(x_{1j} x_{1(j+1)})=n+{4}$, $f(x_{{2}j} x_{{2}(j+1)})={1}$, 其他点和边标号由表 2给出.
表 2(Tab. 2)
表 2 当$n$为奇数时, ${P_2\circ P_n }$的一种$ {(n+4)-(2, 1)}$-全标号方法
Tab. 2 $(n+4)-(2, 1)$-total labelling of $P_2 \circ P_n $, when $n$ is even odd
|
$x_{11} (0)$ |
$x_{12} (1)$ |
$\cdots $ |
$x_{1(n-1)} (1)$ |
$x_{1n} (0)$ |
| $x_{21} (n+4)$ |
2 |
3 |
$\cdots $ |
$n$ |
$n+1$ |
| $x_{22} (n+3)$ |
3 |
4 |
$\cdots $ |
$n+1$ |
2 |
| $\vdots $ |
$\vdots $ |
$\vdots $ |
|
$\vdots $ |
$\vdots $ |
| $x_{2(n-1)} (n+3)$ |
$n$ |
$n+1$ |
$\cdots $ |
$n-2$ |
$n-1$ |
| $x_{2n} (n+4)$ |
$n+1$ |
$n+2$ |
$\cdots $ |
$n-1$ |
$n$ |
|
表 2 当$n$为奇数时, ${P_2\circ P_n }$的一种$ {(n+4)-(2, 1)}$-全标号方法
Tab. 2 $(n+4)-(2, 1)$-total labelling of $P_2 \circ P_n $, when $n$ is even odd
|
(2) 当$d\ge \Delta, n\ge 4$时, 由字典式积的定义可得完全图$K_4$是图$P_2 \circ P_n $的一个子图.
假设图$P_2 \circ P_n $在集合$[0, d+\Delta +1]$上存在一个$(d, 1)$-全标号, 则对于任意一个满足$d(v)=\Delta $的顶点$v$, 都有$f(v)\in\{0, 1, 2, \Delta +d-1, \Delta +d, \Delta +d+1\}$.否则设$f(v)=x$, 当$x\in[3, d-1]$时, 与$v$相关联的边的标号在$[x+d, \Delta +d+1]$中取到, 共有$\Delta+2-x(< \Delta)$种标号, 而由题设知$d(v)=\Delta $, 故推出矛盾; 当$x\in \{d, d+1\}$时, 与$v$相关联的边的标号在$[0, x-d]\cup[x+d, \Delta +d+1]$取到, 共有$\Delta +3-d(< \Delta)$种标号, 矛盾; 当$x\in [d+2, \Delta +d-2]$时, 与$v$相关联的边的标号在$[0, x-d]$中取到, 共有$x+1-d(< \Delta)$种标号, 矛盾.所以对于任意一个度数为$\Delta $的顶点$v$, 一定有$f(v)\in \{0, 1, 2, \Delta +d-1, \Delta +d, \Delta +d+1\}$.下根据图$P_2 \circ P_n$的特点, 分三种情况对满足$d(v)=\Delta$的顶点的标号进行讨论.
由题设条件可以推得$R(d+\Delta +1)=[0, \Delta +1]$, $R(d+\Delta)=[0, \Delta]$, $R(d+\Delta -1)=[0, \Delta-1]$, $R(2)=[d+2, d+\Delta +1]$, $R(1)=[d+1, d+\Delta +1]$, $R(0)=[d, d+\Delta +1]$.
当$d>\Delta +1$时, 通过对$R(x)$的分析可知: $r(0)=\{1, 2\}$, $r(d+\Delta -1)=\{d+\Delta, d+\Delta +1\}$且$r(0)$(或$r(1)$, 或$r(2))\cap r(d+\Delta -1)$(或$r(d+\Delta)$, 或$r(d+\Delta+1))=\varnothing$, 因此对于$d(v)=\Delta$的顶点$v$的标号或者从$\{0, 1, 2\}$中选取, 或者从$\left\{{d+\Delta -1, d+\Delta, d+\Delta +1} \right\}$中选取.而由图$P_2\circ P_n $的特点:至少要有4个度数为$\Delta$且标号不同的顶点才能构成完全图$K_4$, 因此无论哪一种选取方式都不能满足要求, 故推出矛盾.
当$d=\Delta +1$时, 同上可以推出对于满足$d(v)=\Delta$的顶点$v$的标号或者从$\{0, 1, 2, d+\Delta +1\}$中选取, 或者从$\{0, d+\Delta -1, d+\Delta, d+\Delta+1\}$中选取.又由于$R(d+\Delta +1)\cap R(1)=\varnothing $, $R(d+\Delta +1)\cap R(2)=\varnothing $, 故都不能满足要求, 推出矛盾.
当$d=\Delta$时, 由分析知对于$d(v)=\Delta$的顶点$v$的标号若从$\{0, 1, d+\Delta, d+\Delta +1\}$中选取, 则与$R(d+\Delta)\cap R(1)=\varnothing$矛盾; 若从$\{0, 1, 2, d+\Delta, d+\Delta +1\}$中选取, 则与$R(d+\Delta +1)\cap R(2)=\varnothing $矛盾, 类似验证其他方法也不能选取, 推出矛盾.
下面分$n$为偶数和奇数给出图$P_2 \circ P_n $在集合$[0, \Delta+d+2]$上的一种$(d, 1)$-全标号方法.
当$n$为偶数时, 对于$j\in [1, n{-1}]$, 当$j$为奇数时, 令$f(x_{1j} x_{1(j+1)})=d+1$, $f(x_{{2}j} x_{{2}(j+1)})=d+3$; 当$j$为偶数时, 令$f(x_{1j} x_{1(j+1)})=d+{2}$, $f(x_{{2}j}x_{{2}(j+1)})=d+4$.图$P_2 \circ P_n$其他边和点的标号如表 3.
表 3(Tab. 3)
表 3 当$n$为偶数时${P_2 \circ P_n} $的一种${(\Delta +d+2)-(d, 1)}$-全标号方法
Tab. 3 $(\Delta+d+2)-(d, 1)$-total labelling of $P_2 \circ P_n $, when $n$ is even
|
$x_{11} (0)$ |
$x_{12} (1)$ |
$x_{13} (0)$ |
$\cdots $ |
$x_{1(n-1)}(0)$ |
$x_{1n} (1)$ |
| $x_{21} (3)$ |
$d+4$ |
$d+5$ |
$d+6$ |
$\cdots $ |
$d+\Delta $ |
$d+\Delta +1$ |
| $x_{22} (2)$ |
$d+5$ |
$d+6$ |
$d+7$ |
$\cdots $ |
$d+\Delta +1$ |
$d+\Delta +2$ |
| $x_{23} (3)$ |
$d+6$ |
$d+7$ |
$d+8$ |
$\cdots $ |
$d+\Delta +2$ |
$d+5$ |
| $\vdots $ |
$\vdots $ |
$\vdots $ |
$\vdots $ |
|
$\vdots $ |
$\vdots $ |
| $x_{2(n-1)} (3)$ |
$d+\Delta $ |
$d+\Delta +1$ |
$d+\Delta +2$ |
$\cdots $ |
$d+\Delta -2$ |
$d+\Delta -1$ |
| $x_{2n} (2)$ |
$d+\Delta +1$ |
$d+\Delta +2$ |
$d+5$ |
$\cdots $ |
$d+\Delta -1$ |
$d+\Delta $ |
|
表 3 当$n$为偶数时${P_2 \circ P_n} $的一种${(\Delta +d+2)-(d, 1)}$-全标号方法
Tab. 3 $(\Delta+d+2)-(d, 1)$-total labelling of $P_2 \circ P_n $, when $n$ is even
|
当$n$为奇数时, 与$n$为偶数时的标号情况类似, 不再给出证明.
综上所述:当$d\ge \Delta, n\ge 4$时, $\lambda _d^T (P_2 \circ P_n)=d+\Delta +2$.
(3) 若$P_2 \circ P_3$在集合$[0, d+\Delta]$上存在一个$(d, 1)$-全标号, 则对于任意一个满足$d(v)=\Delta $的顶点$v$, 有$f(v)\in\{ 0, 1, d+\Delta -1, d+\Delta \}$.否则与$v$相关联的边至多有$\Delta -1$个标号可以取到, 与已知条件$d(v)=\Delta $矛盾.当$d\geq\Delta +1$时, 因为$r(0)=\{1\}$, $r(1)=\{0\}$, $r(d+\Delta -1)=\{d+\Delta \}$, $r(d+\Delta)=\{d+\Delta -1\}$, 所以对于度数为$\Delta$的顶点, 有$f(v)\in \{0, 1\}$, 或者$f(v)\in \{d+\Delta -1, d+\Delta \}$.由于在$P_2 \circ P_3 $中只有两个顶点$x_{12} $, $x_{22}$的度数为$\Delta$, 其他顶点的度数均为$\Delta -1$, 不失一般性, 设$f(x_{12})=0$, $f(x_{22})=1$, 则对于度数为$\Delta-1$顶点$u$就有$f(u)=2$, 或$f(u)=d+\Delta -2$.因为$R(0)\cap R(d+\Delta -2)=\varnothing$, $R(1)\cap R(d+\Delta -2)=\varnothing$, 所以对于两个相邻顶点$x_{11}$与$x_{21}$就有$f(x_{11})=2$, $f(x_{21})=2$, 这与已知条件(顶点$x_{11}$与$x_{21}$相邻)矛盾, 故此种情况不满足要求.当$d=\Delta$时, 因为$r(d+\Delta-1)={\{}d+\Delta {\}}_{, }r(1)={\{0\}}$, $r(d+\Delta)={\{}d+\Delta-1{\}}$, $r(0)={\{}1, d+\Delta {\}}$, 所以对于度数为$\Delta$的顶点有$f(v)\in{\{}0, 1{\}}$, 或者$f(v)\in \{0, d+\Delta \}$, 或者$f(v)\in{\{}d+\Delta -1, d+\Delta {\}}$.同样可以检验此种情况也不满足要求.
下给出图$P_2 \circ P_3 $在集合$[0, d+\Delta +1]$上的一种$(d, 1)$-全标号方法.
令$f(x_{i1} x_{i2})=d+3$, $f(x_{i2} x_{i3})=d+4$, 其中$i=1, 2$.图$P_2 \circ P_3$的顶点及其他边的标号如表 4所示.
表 4(Tab. 4)
表 4 ${P_2 \circ P_3}$的一种${(\Delta +d+1)-(d, 1)}$-全标号方法
Tab. 4 $(\Delta +d+1)-(d, 1)$-total labelling of $P_2 \circ P_3$
|
$x_{11} (2)$ |
$x_{12} (0)$ |
$x_{13} (2)$ |
| $x_{21} (3)$ |
$d+4$ |
$d+5$ |
$d+6$ |
| $x_{22} (1)$ |
$d+2$ |
$d+1$ |
$d+5$ |
| $x_{23} (3)$ |
$d+5$ |
$d+6$ |
$d+3$ |
|
表 4 ${P_2 \circ P_3}$的一种${(\Delta +d+1)-(d, 1)}$-全标号方法
Tab. 4 $(\Delta +d+1)-(d, 1)$-total labelling of $P_2 \circ P_3$
|
综上所述, 可以得到:当$d\ge n+2, n=3$时, $\lambda _d^T (P_2 \circ P_3)=d+\Delta +1$.
定理4 当$m\ge 4, n\ge 5, d\ge \Delta $时, $\lambda _d^T (P_n \circ P_m)=d+\Delta +2$.
证明 假设图$P_n \circ P_m $在集合$[0, d+\Delta +1]$上存在一个$(d, 1)$-全标号, 则对于任意一个满足$d(v)=\Delta $的顶点, 有$f(v)\in{\{}0, 1, 2, \Delta +d-1, \Delta +d, \Delta +d+1{\}}$, 由定理2(2)中的证明可以得出$\lambda _d^T (P_n \circ P_n)\ge d+\Delta +2=d+2m+4$.对于$P_n \circ P_m $易得$\chi (G)=4, \chi'(G)=\Delta $, 故由引理2可知$\lambda _d^T (P_n \circ P_n)\le \chi(G)+\chi '(G)+d-2=d+\Delta +2$.因此$\lambda _d^T (P_n \circ P_m)=d+\Delta +2$.
定理5 当$n\geq 3$, 若$d\geq \Delta \geq 6$且$n$为偶数时, $\lambda _d^T (P_2 \circ C_n)=\Delta +d+2$; 当$d>\Delta$且$n$为奇数时, $\lambda _d^T (P_2 \circ C_n)=\Delta +d+4$.
证明 由定理2可得:当$d\ge \Delta \ge 3, n\ge 4$时, $\lambda _d^T (P_2 \circ P_n)=\Delta +d+2$, 所以$\lambda_d^T (P_2 \circ C_n)\ge \lambda _d^T (P_2 \circ P_n)=\Delta +d+2$.在对图$P_2 \circ C_n $进行标号时可以仿照图$P_2 \circ P_n$的标号方法得出结论.对于$\lambda _d^T (P_2 \circ C_n)$的上界, 我们分两种情况给出.
当$n$为偶数时, 下面给出图$P_2 \circ C_n $在集合$[0, \Delta+d+2]$上的一种$(d, 1)$-全标号方法.
对于$j\in [1, n{-1}]$, 当$j$为奇数时, 令$f(x_{1j} x_{1(j+1)})=d+1$, $f(x_{{2}j} x_{{2}(j+1)})=d+3$.当$j$为偶数时, 令$f(x_{1j} x_{1(j+1)})=d+{2}$, $f(x_{{2}j} x_{{2}(j+1)})=d+4$.
|
$
f(x_{11} x_{1n} )=d+3, f(x_{21} x_{2n} )=d+4.
$
|
其他点和边的标号方式如表 5所示, 可以得到$\lambda _d^T (P_2 \circ C_n)\le \Delta +d+2$.
表 5(Tab. 5)
表 5 $n$为偶数时, ${P_2 \circ C_n}$的一种${(\Delta +d+2)-(d, 1)}$-全标号方法
Tab. 5 $(\Delta+d+2)-(d, 1)$-total labelling of $P_2 \circ C_n $, when $n$ is even
|
$x_{11} (0)$ |
$x_{12} (1)$ |
$x_{13} (0)$ |
$\cdots $ |
$x_{1(n-1)}(0)$ |
$x_{1n} (1)$ |
| $x_{21} (3)$ |
$d+2$ |
$d+5$ |
$d+6$ |
$\cdots $ |
$d+\Delta $ |
$d+\Delta +1$ |
| $x_{22} (2)$ |
$d+5$ |
$d+6$ |
$d+7$ |
$\cdots $ |
$d+\Delta +1$ |
$d+\Delta +2$ |
| $x_{23} (3)$ |
$d+6$ |
$d+7$ |
$d+8$ |
$\cdots $ |
$d+\Delta +2$ |
$d+5$ |
| $\vdots $ |
$\vdots $ |
$\vdots $ |
$\vdots $ |
|
$\vdots $ |
$\vdots $ |
| $x_{2(n-1)} (3)$ |
$d+\Delta $ |
$d+\Delta +1$ |
$d+\Delta +2$ |
$\cdots $ |
$d+\Delta -2$ |
$d+\Delta -1$ |
| $x_{2n} (2)$ |
$d+\Delta +1$ |
$d+\Delta +2$ |
$d+5$ |
$\cdots $ |
$d+\Delta -1$ |
$d+\Delta $ |
|
表 5 $n$为偶数时, ${P_2 \circ C_n}$的一种${(\Delta +d+2)-(d, 1)}$-全标号方法
Tab. 5 $(\Delta+d+2)-(d, 1)$-total labelling of $P_2 \circ C_n $, when $n$ is even
|
当$n$为奇数时, 由于$C_1 =x_{11} x_{12} \cdots x_{1n} x_{11} $, $C_2 =x_{21} x_{22} \cdots x_{2n} x_{21} $是奇圈, 所以对图$P_2\circ C_n $进行标号时, 必须保证每一个奇圈$C_i (i=1, 2)$中的顶点至少有3个不同的标号, 即对于图$P_2 \circ C_n$的顶点来说至少要有6个不同的顶点标号.假设图$P_2 \circ C_n$在$[0, \Delta +d+3]$上存在一个$(d, 1)$-全标号, 则对任意一点$v\in V(P_2 \circ C_n)$, 必有$f(v)\in [0, 4]\cup[\Delta +d-1, \Delta +d+3]$.同定理2(2)的证法即可得到当$d>\Delta$时, 无论如何选取图$P_2 \circ C_n $顶点的标号都不能满足要求, 故矛盾.下面给出图$P_2 \circ C_n $在集合$[0, \Delta+d+4]$上的一种$(d, 1)$-全标号方法.
对于$j\in [1, n{-1}]$, 当$j$为奇数时, 令$f(x_{1j} x_{1(j+1)})=d+1$, $f(x_{{2}j} x_{{2}(j+1)})=d+3$; 当$j$为偶数时, 令$f(x_{1j} x_{1(j+1)})=d+{3}$, $f(x_{{2}j} x_{{2}(j+1)})=d+4$, 当$j=n$时, 令
|
$
f(x_{1(n-1)} x_{1n} )=f(x_{2(n-1)} x_{2n} )=d+5,
\\
f(x_{11} x_{1n} )=d+4, f(x_{21} x_{2n} )=d+\Delta +4.
$
|
其他点和边的标号方式由表 6给出, 由此可以得到$\lambda _d^T (P_2\circ C_n)\le \Delta +d+4$.
表 6(Tab. 6)
表 6 $n$为奇数时, ${P_2 \circ C_n }$的一种${(\Delta +d+{4})-(d, 1)}$-全标号方法
Tab. 6 $(\Delta+d+2)-(d, 1)$-total labelling of $P_2 \circ C_n $, when $n$ is odd
|
$x_{11} (0)$ |
$x_{12} (1)$ |
$x_{13} (0)$ |
$\cdots $ |
$x_{1(n-1)}(1)$ |
$x_{1n} (4)$ |
| $x_{21} (2)$ |
$d+5$ |
$d+6$ |
$d+7$ |
$\cdots $ |
$d+\Delta +1$ |
$d+\Delta +2$ |
| $x_{22} (3)$ |
$d+6$ |
$d+7$ |
$d+8$ |
$\cdots $ |
$d+\Delta +2$ |
$d+\Delta +3$ |
| $x_{23} (2)$ |
$d+7$ |
$d+8$ |
$d+9$ |
$\cdots $ |
$d+\Delta +3$ |
$d+\Delta +4$ |
| $\vdots $ |
$\vdots $ |
$\vdots $ |
$\vdots $ |
|
$\vdots $ |
$\vdots $ |
| $x_{2(n-1)} (3)$ |
$d+\Delta +1$ |
$d+\Delta +2$ |
$d+\Delta+3$ |
$\cdots $ |
$d+\Delta -1$ |
$d+\Delta $ |
| $x_{2n} (5)$ |
$d+\Delta +2$ |
$d+\Delta +3$ |
$d+6$ |
$\cdots $ |
$d+\Delta $ |
$d+\Delta +1$ |
|
表 6 $n$为奇数时, ${P_2 \circ C_n }$的一种${(\Delta +d+{4})-(d, 1)}$-全标号方法
Tab. 6 $(\Delta+d+2)-(d, 1)$-total labelling of $P_2 \circ C_n $, when $n$ is odd
|
定理6 当$m\ge 4, n\ge 5, d\ge \Delta $时, 若$m$为偶数, 则$\lambda _d^T (P_n \circ C_m)=d+\Delta +2$; 若$m$为奇数, 则$\lambda _d^T (P_n \circ C_m)=d+\Delta +4$.
证明 由定理2得:当$m\geq 4$, $n\geq{4}$, $d\geq\Delta$时, $\lambda _d^T (P_n \circ P_m)=d+\Delta +2$.所以$\lambda _d^T (P_n \circ C_m)\ge \lambda _d^T (P_n \circ P_m)=d+\Delta +2$.下面分情况给出图$P_n \circ C_m $的一种$(d, 1)$-全标号方法(见表 6).
① $m$为偶数、$n$为偶数
令
|
$
\begin{align*}
&f(x_{ij} )=\left\{ \begin{array}{l}
&0, i=1, 3, 5, \cdots, n-1, j=1, 3, 5, \cdots, m-1, \\
& 1, i=1, 3, 5, \cdots, n-1, j=2, 4, 6, \cdots, m, \\
&2, i=2, 4, 6, \cdots, n, j=2, 4, 6, \cdots, m, \\
&3, i=2, 4, 6, \cdots, n, j=1, 3, 5, \cdots, m-1;
\end{array} \right.\\
&f(x_{ij} x_{i(j+1)})=\left\{ \begin{array}{l}
&d+1, i=1, 3, 5, \cdots, n-1, j=1, 3, 5, \cdots, m-1, \\
& d+2, i=1, 3, 5, \cdots, n-1, j=2, 4, 6, \cdots, m-2, \\
&d+3, i=2, 4, 6, \cdots, n, j=2, 4, 6, \cdots, m-2, \\
&d+4, i=2, 4, 6, \cdots, n, j=1, 3, 5, \cdots, m-1;
\end{array} \right.\\
&f(x_{i1} x_{im} )=\left\{ \begin{array}{l}
&d+2, i=1, 3, 5, \cdots, n-1, \\
& d+3, i=2, 4, 6, \cdots, n;
\end{array} \right.\\
&f(x_{i1} x_{(i+1)1} )=\left\{ \begin{array}{l}
&d+\Delta +2, i=1, 3, 5, \cdots, n-1, \\
&d+m+4, i=2, 4, 6, \cdots, n-2.
\end{array} \right.
\end{align*}
$
|
其他边的标号方式同$n$为偶数时图$P_n \circ P_m$的边标号方法一样, 以下不再赘述.
根据上述的标号方法可以得到图$P_n \circ C_m $的每条边$x_{ij}x_{kt} (i\ne k, t\ne j+1)$都可以取到合适的标号.且对于$m$为偶数, $n$为奇数, 此结论仍然成立.
② $m$为奇数、$n$为偶数
由于图$P_n \circ C_m$中含有$n$个奇圈$C_i =x_{i1} x_{i2} \cdots x_{im} x_{i1} (i=1, 2, \cdots, n)$, 所以可以得到$\lambda _d^T (P_n\circ C_m)\ge d+\Delta +4$.下面给出图$P_n \circ C_m $在$[0, d+\Delta +4]$上的一种$(d, 1)$-全标号方法.
令
|
$
\begin{align*}
&f(x_{im} )=\left\{ \begin{array}{l}
&4, i=1, 3, 5, \cdots, n-1, \\
&5, i=2, 4, 6, \cdots, n;
\end{array} \right.\\
\end{align*}
$
|
|
$
\begin{align}
&f(x_{ij} )=\left\{ \begin{array}{l}
&0, i=1, 3, 5, \cdots, n-1, j=1, 3, 5, \cdots, m-2, \\
& 1, i=1, 3, 5, \cdots, n-1, j=2, 4, 6, \cdots, m-1, \\
&2, i=2, 4, 6, \cdots, n, j=1, 3, 5, \cdots, m-2, \\
&3, i=2, 4, 6, \cdots, n, j=2, 4, 6, \cdots, m-1;
\end{array} \right.\\
&f(x_{ij} x_{i(j+1)} )=\left\{ \begin{array}{l}
& d+1, i=1, 3, 5, \cdots, n-1, j=1, 3, 5, \cdots, m-2, \\
&d+2, i=1, 3, 5, \cdots, n-1, j=2, 4, 6, \cdots, m-3, \\
&d+3, i=2, 4, 6, \cdots, n, j=1, 3, 5, \cdots, m-2, \\
&d+4, i=2, 4, 6, \cdots, n, j=2, 4, 6, \cdots, m-3, \\
&d+5, i=1, 3, 5, \cdots, n, j=m-1;
\end{array} \right.\\
&f(x_{i1} x_{im} )=\left\{ \begin{array}{l}
&d+4, \qquad i=1, 3, 5, \cdots, n-1, \\
&d+\Delta +4, i=2, 4, 6, \cdots, n;
\end{array} \right.\\
&f(x_{i1} x_{(i+1)1} )=\left\{ \begin{array}{l}
& d+2, i=1, 3, 5, \cdots, n-1, \\
& d+3, i=2, 4, 6, \cdots, n-2;
\end{array} \right.\\
&f(x_{i1} x_{(i-1)1} )=d+3+t, t\in [2, m], i\in \{2, 4, \cdots
,
n\}; \\
&f(x_{i1} x_{(i+1)t} )=d+m+3+t, t\in [2, m], i\in \{2, 4,
\cdots, n-2\};
\\
&f(x_{ij} x_{(i-1)t} )=d+2+j+t, t\in [1, m], i\in \{2, 4,
\cdots, n\}, j\in [2, m];
\\
&f(x_{ij} x_{(i+1)t} )=d+m+2+j+t, t\in [1, m], i\in
\{2, 4, \cdots, n-2\}, j\in [2, 4];\\
&f(x_{ij} x_{(i+1)t} )=\left\{ \begin{array}{l}
& d+m+2+j+t, t\in [1, m+4-j], \\
& d-m+2+j+t, t\in [m+5-j, m],
\end{array} \right.\\
&\qquad\qquad\qquad i\in \{2, 4, \cdots, n-2\}, j\in [5, m];\\
&f(x_{im} x_{(i+1)t} )=\left\{ \begin{array}{l}
& d+2m+2+t, t\in [1, 3], i\in \{2, 4, 6, \cdots, n-2\}, \\
& d+2+t, \qquad\;\; t\in [4, m], i\in \{2, 4, 6, \cdots, n-2\}.
\end{array} \right.
\end{align}
$
|
易观察发现上述标号方式符合要求.同样可以验证, 对于$m$为奇数、$n$为奇数时, 此结论依然成立.从而得到:当$m$为奇数时, $\lambda_d^T (P_n \circ C_m)=d+\Delta +4$.
综上可得: $m$为偶数时, $\lambda _d^T (P_n \circ C_m)=d+\Delta+2$; $n$为奇数时, $\lambda _d^T (P_n \circ C_m)=d+\Delta +4$.
