由信息科学、计算机科学、生物学等提出的点可区别边染色(或强边染色)^{[1, 2]}是一个十分困难的问题, 文[3]提出了距离不超过$\beta$的任意两点可区别的边染色概念及相关猜想, 文[4]提出了图的邻强边染色概念, 得到了若干结果, 并提出了有关猜想.张忠辅等人于2008年在文[5]中又提出了图的点可区别均匀边染色概念和猜想, 得到了星、完全图、扇、轮和完全二部图等简单图的点可区别均匀边色数.

最近, 图的在新染色概念下的染色问题是非常活跃的课题, 但要确定其相应的染色数是非常困难的.文[6]探讨了一些倍图的邻点可区别均匀全色数, 文[7]研究了一些Mycielski图的点可区别均匀全染色问题, 给出了路、圈、星和扇的Mycielski图的点可区别均匀全色数.文[8]得到了路和圈的Mycielski图的点可区别边色数, 文[9]给出了路、圈和星的Mycielski图的Smarandchely-邻点可区别边色数.文[10, 11]研究了一些图的点可区别均匀边染色问题, 分别给出了星、扇和轮的倍图的点可区别均匀边色数, 以及等阶的路和路、路和圈、圈和圈的联图的点可区别均匀边色数.本文给出了积图$G\times G$的点可区别均匀边色数的一个结论, 得到了$K_n\times K_n$、$S_n\times S_n$和$W_n\times W_n$的点可区别均匀边色数.

定义 2.1^{[12, 13]} 设有简单图$G$和正整数$k$, 若存在映射$f:~E(G)\rightarrow\{1, 2, \cdots, k\}$, 满足任意相邻的边$e, e^\prime$有~$f(e)\not=f(e^\prime)$, 则称$f$为$G$的一个正常边染色法(简记为$k$-PEC).而称

$ \chi^\prime(G)=\text{min}\{k|G\text{存在一个}k\text{-PEC}\} $

为$G$的边色数.

定义 2.2 ^[1-3] 对$|V(G)|\geq3$的连通图$G(V, E)$的$k$-正常边染色法$f$, 若满足$\forall u, v\in V(G), ~u\not=v, ~C(u)\not=C(v)$, 则称$f$为$G$的一个$k$-点可区别边染色法(简记为$k$-VDEC).而

$ \chi^\prime_{\text{vd}}(G)=\text{min}\{k|G\text{存在一个}k\text{-VDEC}\} $

称为$G$的点可区别边色数.其中$C(u)=\{f(uv)|uv\in E(G)\}$称为点$u$在$f$下的关联边色集, $C(u)$在色全集合$C=\{1, 2, \cdots, k\}$中的补集记为$\overline{C}(u)=C\backslash C(u)$.

定义 2.3^{[5, 10, 11]} 对$|V(G)|\geq3$的连通图$G(V, E)$的$k$-点可区别边染色法$f$, 若满足$\forall i, j\in\{1, 2, \cdots, k\}, ~||E_{i}|-|E_{j}||\leq1$, 则称$f$为$G$的一个$k$-点可区别均匀边染色法(简记为$k$-VDEEC).而

$ \chi^\prime_{\text{vde}}(G)=\text{min}\{k|G\text{存在一个}k\text{-VDEEC}\} $

称为$G$的点可区别均匀边色数.其中$E_i=\{e|e\in E(G), f(e)=i\}, ~i=1, 2, \cdots, k.$

定义 2.4  对简单图$G$, $\delta(G)$和$\Delta(G)$分别表示$G$的最小度和最大度, $n_i$表示$G$中度为$i$的点数, $(^n_m)$表示$n$个元素中取$m$个元素的组合数, 则称$\mu(G)=\text{max}\{\text{min}\{\theta|(^\theta_i)\geq n_i\}, ~\delta(G)\leq i\leq \Delta(G)\}$为$G$的组合度.

猜想 2.1(VDECC)^[1-3] 对$|V(G)|\geq3$的简单连通图$G$, 有

$ \chi^\prime_{\text{vd}}(G)\leq\mu(G)+1. $

猜想 2.2(VDEECC)^{[5, 10, 11]} 对$|V(G)|\geq3$的简单连通图$G$, 有

$ \chi^\prime_{\text{vde}}(G)\leq\mu(G)+1~\text{且}~ \chi^\prime_{\text{vde}}(G)=\chi^\prime_{\text{vd}}(G). $

定义 2.5^[13] 设$G$和$H$是两个简单图, 记$G$和$H$的顶点集分别为$V(G)=\{u_1, u_2, \cdots, u_m\}$, $V(H)=\{v_1, v_2, \cdots, v_n\}$.若满足$V(G\times H)=\{w_{ij}|w_{ij}=(u_i, v_j), ~1\leq i\leq m, ~1\leq j\leq n\}$, $E(G\times H)=\{w_{ij}w_{lk}|i=l\text{且}v_jv_k\in E(H), ~\text{或}j=k\text{且}u_iu_l\in E(G), ~1\leq i, l\leq m, ~1\leq j, k\leq n\}$, 则称$G\times H$为$G$与$H$的积图.

由定义2.2和定义2.3知, 下述引理2.1显然成立.

引理 2.1  对$|V(G)|\geq3$的简单连通图$G$, 有

$ \chi^\prime_{\text{vde}}(G)\geq\chi^\prime_{\text{vd}}(G)\geq\mu(G). $

引理 2.2^[5] 当$n\geq3$时, 对$n$阶的完全图$K_n$, 有

$ \chi^\prime_{\text{vde}}(K_n)=\left\{ \begin{array}{ll} n, \hspace{8mm}n\equiv1(\text{mod}~2); \\n+1, \hspace{2mm}n\equiv0(\text{mod}~2). \end{array} \right. $

引理 2.3^[13] 当$n\geq2$时, 对$n$阶的完全图$K_n$, 有

$ \chi^\prime(K_n)=\left\{ \begin{array}{ll} n, \hspace{8mm}n\equiv1(\text{mod}~2); \\n-1, \hspace{2mm}n\equiv0(\text{mod}~2). \end{array} \right. $

引理 2.4^[5] 当$n\geq2$时, 对$n+1$阶的星$S_n$, 有

$ \chi^\prime_{\text{vde}}(S_n)=n. $

引理 2.5^[5] 当$n\geq3$时, 对$n+1$阶的轮$W_n$, 有

$ \chi^\prime_{\text{vde}}(W_n)=\left\{ \begin{array}{ll} 5,\hspace{2mm}n=3; \\n,\hspace{2mm}n\geq4. \end{array} \right. $

文中未加述及的术语、记号可参见文献[12, 13].

定理 3.1  若简单图$G$的 $\chi^\prime_{\text{vde}}(G)=\Delta(G)$, 且$|E(G)|\equiv0(\text{mod}~\Delta(G))$, 则

$ \chi^\prime_{\text{vde}}(G\times G)=2\Delta(G). $

证  由于$\chi^\prime_{\text{vde}}(G)=\Delta(G)$, 所以$G$有唯一最大度点, 否则 $\chi^\prime_{\text{vde}}(G)\geq\Delta(G)+1$, 这与已知相矛盾.从而$G\times G$有唯一最大度点, 且$\Delta(G\times G)=2\Delta(G)$.又因

$ \text{min}\{\theta|(^\theta_{2\Delta(G)})\geq 1\}=2\Delta(G), $

所以由组合度定义知 $\mu(G\times G)\geq2\Delta(G)$.所以由引理2.1知 $\chi^\prime_{\text{vde}}(G\times G)\geq2\Delta(G)$, 要证定理为真, 仅需给出$G\times G$的一个$(2\Delta(G))$-VDEEC.

为了便于区别, 下面将$G\times G$表示为$G_1\times G_2$.在$G_1\times G_2$中, $G_1$的所有拷贝是两两不交的, 记它们的并集为$H_1$, 同样, $G_2$的所有拷贝是两两不交的, 它们的并集记为$H_2$.则$H_1$与$H_2$是边不交的, 且$G_1\times G_2=H_1\bigcup H_2$.因为 $\chi^\prime_{\text{vde}}(G_1)=\chi^\prime_{\text{vde}}(G_2)=\Delta(G)$, 设色全集合$C=\{1, 2, \cdots, 2\Delta(G)\}$, 分两步构造染色$f$如下.

第一步  用色集$\{1, 2, \cdots, \Delta(G)\}$对$G_1$的每一拷贝$G_1\times\{v_j\}, ~v_j\in V(G_2)$进行点可区别均匀边染色, 且让每一拷贝对应$G_1$的同一边的边都着以同一色.

第二步  用色集$\{\Delta(G)+1, \Delta(G)+2, \cdots, 2\Delta(G)\}$对$G_2$的每一拷贝$\{u_i\}\times G_2, ~u_i\in V(G_1)$进行点可区别均匀边染色, 且让每一拷贝对应$G_2$的同一边的边都着以同一色.

显然, 上述染色法$f$对$G\times G$(即$G_1\times G_2$)是点可区别的.由于$G$的$(\Delta(G))$-VDEEC法中每一色使用了$\frac{|E(G)|}{\Delta(G)}$次, 又$G_1\times G_2$中$G_1$和$G_2$分别被拷贝了$|V(G)|$次, 从而$f$对$G\times G$, 有

$ \forall i\in\{1, 2, \cdots, 2\Delta(G)\}, ~|E_i|=\frac{|E(G)|\cdot|V(G)|}{\Delta(G)}. $

即$f$是均匀的.总之, $f$是$G\times G$的$(2\Delta(G))$-VDEEC.因此, 定理为真.

定理 3.2  当$n\geq2$时, 对两个$n$阶的完全图$K_n$与$K^\prime_n$的积图$K_n\times K^\prime_n$, 有

$ \chi^\prime_{\text{vde}}(K_n\times K^\prime_n)=2n. $

证  记$n$阶完全图$K_n$与$K^\prime_n$的顶点集分别为

$ V(K_n)=\{u_1, u_2, \cdots, u_n\}, ~V(K^\prime_n)=\{v_1, v_2, \cdots, v_n\}. $

显然$K_n\times K^\prime_n$为$(2n-2)$ -正则图, 且$|V(K_n\times K^\prime_n)|=n^2$, 组合度

$ \mu(K_n\times K^\prime_n)=\text{min}\{\theta|(^\theta_{2n-2})\geq n^2\}=2n. $

由引理2.1知 $\chi^\prime_{\text{vde}}(K_n\times K^\prime_n)\geq2n$, 要证定理为真, 仅需给出$K_n\times K^\prime_n$的一个$(2n)$-VDEEC.设色全集合$C=\{1, 2, \cdots, 2n\}$, 以下分两种情况予以证明.

情形 1 当$n\equiv1(\text{mod}~2)$时, 由引理2.2知此时 $\chi^\prime_{\text{vde}}(K_n)=n$.分两步构造染色$f$如下.

第一步  用色集$\{1, 2, \cdots, n\}$对$K_n$的每一拷贝$K_n\times\{v_j\}, ~v_j\in V(K^\prime_n)$ $~(j=1, 2, \cdots, n)$进行点可区别均匀边染色, 且让每一拷贝对应$K_n$的同一边的边都着以同一色.

第二步  用色集$\{n+1, n+2, \cdots, 2n\}$对$K^\prime_n$的每一拷贝$\{u_i\}\times K^\prime_n, ~u_i\in V(K_n)~~$ $ (i=1, 2, \cdots, n)$进行点可区别均匀边染色, 让每一拷贝对应$K^\prime_n$的同一边的边都着以同一色.则$f$对$K_n\times K^\prime_n$, 有

$ \forall i\in C, ~|E_i|=\frac{n(n-1)}{2}. $

自然, $f$是$K_n\times K^\prime_n$的$(2n)$-VDEEC.

情形 2 当$n\equiv0(\text{mod}~2)$时, 由引理2.3知此时 $\chi^\prime(K_n)=n-1$.分两步构造染色$f$如下.

第一步  用色集$\{1, 2, \cdots, n\}\setminus\{j\}$对$K_n$的每一拷贝$K_n\times\{v_j\}, ~v_j\in V(K^\prime_n)$进行正常边染色, $j=1, 2, \cdots, n$.

第二步  用色集$\{n+1, n+2, \cdots, 2n\}\setminus\{n+i\}$对$K^\prime_n$的每一拷贝$\{u_i\}\times K^\prime_n, ~u_i\in V(K_n)$进行正常边染色, $i=1, 2, \cdots, n$.

由于$n$阶完全图的每个顶点关联边数恰好是$n-1$, 则$f$对$K_n\times K^\prime_n$, 有

$ \overline{C}(w_{ij})=\{j, n+i\}, ~i, j=1, 2, \cdots, n, $

$ \forall i\in\{1, 2, \cdots, 2n\}, ~|E_i|=\frac{n(n-1)}{2}. $

所以, $f$是$K_n\times K^\prime_n$的$(2n)$-VDEEC.

总之, 定理为真.

推论 3.1  当$n\geq2$时, 对$n+1$阶的星$S_n$, 有

$ \chi^\prime_{\text{vde}}(S_n\times S_n)=2n. $

证  由引理2.4知 $\chi^\prime_{\text{vde}}(S_n)=n=\Delta(S_n)$, 又$|E(S_n)|=n$, 所以$|E(S_n)|\equiv0(\text{mod}~\Delta(S_n))$, 由定理3.1知结论成立.

推论 3.2  当$n\geq3$时, 对$n+1$阶的轮$W_n$, 有

$ \chi^\prime_{\text{vde}}(W_n\times W_n)=\left\{ \begin{array}{ll} 8, \hspace{4mm}n=3; \\2n, \hspace{2mm}n\geq4. \end{array} \right. $

证  当$n=3$时, 显然$W_3\times W_3\cong K_4\times K_4$, 由定理3.2知此时结论成立.当$n\geq4$时, 由引理2.5知 $\chi^\prime_{\text{vde}}(W_n)=n=\Delta(W_n)$, 又$|E(W_n)|=2n$, 所以$|E(W_n)|\equiv0(\text{mod}~\Delta(W_n))$, 由定理3.1知结论成立.

由此可见, 等阶的完全图与完全图、星与星、轮与轮的积图对点可区别边染色猜想2.1和点可区别均匀边染色猜想2.2(即VDECC和VDEECC)成立.