几类笛卡尔乘积图的邻点全和可区别全染色

2022-04-22叶宏波殷志祥

广州大学学报（自然科学版） 2022年1期

叶宏波，杨超*，殷志祥，姚兵

(1.上海工程技术大学数理与统计学院/智能计算与应用统计研究中心, 上海 201620; 2.西北师范大学数学与统计学院, 甘肃兰州 730070)

0 引言

图的染色问题是图论中的重要问题之一，在数学、化学和计算机科学等领域有广泛的应用，具体涉及排课问题、交通问题、电路设计问题和无线电通讯频道分配问题等。从最初的点染色[1]、边染色[2]和全染色[3-5]，再到后来的(邻)点可区别边染色[6]、(邻)点可区别全染色[7-8]、邻和可区别边染色[9-10]和邻和可区别全染色[11-13]等，染色问题一直都是学者们关注和研究的热点。2017年，Flandrin等[14]定义了图的邻点全和可区别全染色，目前此类染色还有待进一步研究。本文将对几类笛卡尔积图的邻点全和可区别全染色问题进行深入探讨。

文中V(G)、E(G)和Δ(G)分别表示图G的顶点集、边集和顶点的最大度，集合[a,b]={a,a+1,…,b} (a

2021年，Chang等(1)Chang J Z, Yang C, Yin Z X, et al. Neighbor full sum distinguishing non-proper total coloring of graphs[J]. Submitted to Journal, 2021.研究了路、圈、三正则图、星、完全图、超立方图、二部图、完全r-部图的邻点全和可区别全染色，并提出下述猜想：

猜想[15]：对于任意一个阶数至少为3的简单连通图G，都有fgndi∑(G)≤3。

定义2设G1=(V1,E1)与G2=(V2,E2)是2个简单连通图，G1与G2的笛卡尔乘积图定义为G1×G2=(V,E)，其中,V=V1×V2={(ui,vj)|ui∈V1,vj∈V2}，

E={((u1,v1), (u2,v2))|v1=v2且(u1,u2)∈E1，或u1=u2且(v1,v2)∈E2}。

本文研究了几类笛卡尔乘积图的邻点全和可区别非正常全染色，所得结论证实了上述猜想。

1 路、圈之间的笛卡尔乘积图

本文中路、圈之间的笛卡尔乘积图分为：①路与路笛卡尔乘积图；②路与圈笛卡尔乘积图；③圈与圈笛卡尔乘积图。本文定义Gm×Hn表示有m行和n列，其中,vi, j表示第i行第j列的点。

定理1fgndi∑(Pm×Pn)=2。

证明易得fgndi∑(P2×P2)=2。由于m为奇数，n为偶数，与m为偶数，n为奇数时Pm×Pn结构相同，所以下面分3种情况讨论。

情形1.m≡1(mod 2),n≡1(mod 2)。

首先令f(vi, j)=2(i≡0(mod 2),j≡0(mod 2))，其余点和边均染1。

此时各点的权重为：φ(v1,1)=φ(v1,n)=φ(vm,1)=φ(vm,n)=5；

φ(vi, j)=8(i=1,m,j≡0(mod 2);i≡0(mod 2),j=1,n)；

φ(vi, j)=7(i=1,m,j≡1(mod 2),j≠1,n;i≡1(mod 2),i≠1,m,j=1,n)；

φ(vi, j)=9(i≡1(mod 2),i≠1,m,j≡1(mod 2),j≠1,n)；

φ(vi, j)=10(i≡0(mod 2),j≡0(mod 2))；

φ(vi, j)=11(i≡0(mod 2),j≡1(mod 2),j≠1,n;i≡1(mod 2),i≠1,m,j≡0(mod 2))。

情形2.m≡0(mod 2),n≡0(mod 2)。

令f(vi, j)=2(i≡0(mod 2),i≠m,j≡0(mod 2),j≠n)，f(vm-1, jvm, j)=f(vi,n-1vi,n)=2 (i≡0(mod 2),i≠m,j≡0(mod 2),j≠n)，其余点和边均染1。

此时各点权重为：φ(v1,1)=φ(v1,n)=φ(vm,1)=φ(vm,n)=5；

φ(vi, j)=7(i=1,m,j≡1(mod 2),j≠1;i≡1(mod 2),i≠1,j=1,n)；

φ(vi, j)=8(i=1,m,j≡0(mod 2),j≠n;i≡0(mod 2),i≠m,j=1,n)；

φ(vi, j)=9(i≡1(mod 2),i≠1,j≡1(mod 2),j≠1)；

φ(vi, j)=10(i≡0(mod 2),i≠m,j≡0(mod 2),j≠n)；

φ(vi, j)=11(i≡0(mod 2),i≠m,j≡1(mod 2),j≠1;i≡1(mod 2),i≠1,j≡0(mod 2),j≠n)。

情形3.m≡0(mod 2),n≡1(mod 2)。

此时令f(vi, j)=2(i≡0(mod 2),i≠m,j≡0(mod 2))，f(vm-1, jvm, j)=2(j≡0(mod 2))，其余点和边均染1。

则各点的权重为：φ(v1,1)=φ(vm,1)=φ(v1,n)=φ(vm,n)=5；

φ(vi, j)=8(i=1,m,j≡0(mod 2);i≡0(mod 2),i≠m,j≡0(mod 2))；

φ(vi, j)=7(i=1,m,j≡1(mod 2),j≠1,n;i≡1(mod 2),i≠1,j=1,n)；

φ(vi, j)=9(i≡1(mod 2),i≠1,j≡1(mod 2),j≠1,n)；

φ(vi, j)=10(i≡0(mod 2),i≠m,j≡0(mod 2))；

φ(vi, j)=11(i≡0(mod 2),i≠n,j≡1(mod 2),j≠1;i≡1(mod 2),i≠1,m,j≡0(mod 2))。

综上3种情形可得任意相邻两点的权重各不相等，即fgndi∑(Pm×Pn)≤2，又fgndi∑(Pm×Pn)≥2，所以fgndi∑(Pm×Pn)=2。

定理2fgndi∑(Pm×Cn)=2。

证明以下分4种情形进行讨论。

情形1.m≡0(mod 2),n≡1(mod 2)。

此时令f(vi, j)=2(i≡0(mod 2),j≡0(mod 2))，其余点和边均染1。

则各点的权重为：φ(vi, j)=7(i≡1(mod 2),j=1,n)；

φ(vi, j)=8(i≡0(mod 2),j=1,n)；

φ(vi, j)=9(i≡1(mod 2),j≡1(mod 2),j≠1,n)；

φ(vi, j)=10(i≡0(mod 2),j≡0(mod 2))；

φ(vi, j)=11(i≡1(mod 2),j≡0(mod 2);i≡0(mod 2),j≡1(mod 2),j≠1,n)。

情形2.m≡1(mod 2),n≡1(mod 2)。

由于m-3≡0(mod 2),所以可令f(vi, j)=2(i≡1(mod 2),i>3,j≡0(mod 2))，

f(e0)=f(v0)=1(e0∈E(G1),v0∈V(G1){vi, j}),其中(G1=Pk×Pn,k∈[4,m])；

f(v1, jvm, j)=1。f(v1, jv1, j+1)=2(j≠n);f(v1, jv2, j)=2;f(v3, j)=2(j≡0(mod 2))；

f(v2, jv3, j)=f(v3, jv4, j)=2(j≡0(mod 2))；f(v3, jv3, j+1)=2(j≡0(mod 2),j≠2)；

f(v3,1v3,2)=2；f(e1)=f(v1)=1(e1∈E(G)E0,v1∈V(G)V0)(E0表示上述已染色的边集，V0表示上述已染色的点集)。

此时,各点的权重为：φ(u)(u∈V(G1){v4, j})同情形1，其余点的权重如下：

φ(v4,1)=φ(v4,n)=7；φ(v2,1)=φ(v2,n)=8；φ(vi, j)=9(i=1,3,j=1,n)；

φ(v4, j)=9(j≡1(mod 2),j≠1,n)；φ(v2, j)=10(j≡1(mod 2),j≠1,n)；

φ(v2,3)=11；φ(vi, j)=13(i=1,3,j≡0(mod 2))；

φ(vi, j)=12(i=1,j≡1(mod 1),j≠1,n;i=2,4,j≡0(mod 2);i=3,j≡1(mod 2),j≠1,3,n)

情形3.m≡0(mod 2),n≡0(mod 2)。

f(vi, j)=2(i≡0(mod 2),j≡0(mod 2),j≠n)；f(vi,n-1vi,n)=2(i≡0(mod 2))；

f(e2)=f(v2)=1(e2∈E(G)E1,v2∈V(G)V1)(E1表示上述已染色的边集，V1表示上述已染色的点集)。此时各点的权重如下：

φ(vi, j)=7(i≡1(mod 2),j=1,n)；φ(vi, j)=8(i≡0(mod 2),j=1,n)；

φ(vi, j)=9(i≡1(mod 2),i≠1,j≡1(mod 2),j≠1)；

φ(vi, j)=10(i≡0(mod 2),j≡0(mod 2),j≠n)；

φ(vi, j)=11(i≡1(mod 2),j≡0(mod 2),j≠n;i≡0(mod 2),j≡1(mod 2),j≠1)。

情形4.m≡1(mod 2),n≡0(mod 2)。

f(vi, j)=2(i≡1(mod 2),i≠1,j≡0(mod 2),j≠n)；f(vi,n-1vi,n)=2(i≡1(mod 2),i≠1)；

f(v1,1)=f(v1,n)=f(v1, jv1, j+1)=2(j≠n)；f(v1, jv2, j)=2。其余点和边均染色1。

则各点的权重为:φ(vi, j)=7(i≡0(mod 2),i≠2,j=1,n)；

φ(vi, j)=8(i≡1(mod 2),i≠1,m,j=1,n)；

φ(vi, j)=9(i=2,m-1,j=1,n;i≡0(mod 2),i≠2,j≡1(mod 2),j≠1)；

φ(vi, j)=10(i=1,j=1,n;i≡1(mod 2),i≠1,j≡0(mod 2),j≠n;i=2,j≡1(mod 2),j≠1)；

φ(vi, j)=11(i≡0(mod 2),j≡0(mod 2),j≠n;i≡1(mod 2),i≠1,j≡1(mod 2),j≠1)；

φ(vi, j)=12(i=1,j≡1(mod 2),j≠1,n-1)；

φ(vi, j)=13(i=1,j≡0(mod 2),j≠2,n)；

φ(vi, j)=14(i=1,j=2,n-1)。

由上述4种情形可得任意相邻两点的权重各不相等，即fgndi∑(Pm×Cn)≤2，

又fgndi∑(Pm×Cn)≤2，因此，fgndi∑(Pm×Cn)=2。

定理3fgndi∑(Cm×Cn)=2(m,n>6)。

证明由于Cm×Cn在m、n分别为奇数和偶数的结构与m、n分别为偶数和奇数时相同，故以下考虑3种情况即可。

情形1.m≡0(mod 2),n≡0(mod 2)。

令f(vi, j)=2(i≡1(mod 2),j≡0(mod 2))，其余点和边均染1。

则各点的权重为:φ(vi, j)=9(i≡0(mod 2),j≡1(mod 2))；

φ(vi, j)=10(i≡1(mod 2),j≡0(mod 2))；

φ(vi, j)=11(i≡1(mod 1),j≡1(mod 2);i≡0(mod 2),j≡0(mod 2))。

情形2.m≡0(mod 2),n≡1(mod 2)。

令f(vi, j)=2(i≡1(mod 2),j≡1(mod 2))；f(vi,nvi,1)=2(i≡1(mod 2))；

f(vi,1vi,2)=2(i≡1(mod 2))；f(vi,1vi+1,1)=2(i≡1(mod 2))；其它均为1。

则各点的权重为：φ(vi, j)=9(i≡0(mod 2),j≡0(mod 2))；

φ(vi, j)=10(i≡1(mod 2),j≡1(mod 2),j≠1,n)；

φ(vi, j)=11(i≡1(mod 2),j≡0(mod 2),j≠2;i≡0(mod 2),j≡1(mod 2),j≠1)；

φ(vi, j)=12(i≡1(mod 2),j=2,n;i≡0(mod 2),j=1)；

φ(vi, j)=14(i≡1(mod 2),j=1)。

情形3.m≡1(mod 2),n≡1(mod 2)(m>6,n>6)。

令f(vi, j)=2(i≡1(mod 2),j≡1(mod 2),(i≠m,j≠1))；

f(vi,nvi,1)=2(i≡1(mod 2),i≠m)；f(vi,1vi,2)=2(i≡1(mod 2))；

f(vi,1vi+1,1)=2(i≡1(mod 2),i≠m)；f(vm, jv1, j)=2(j≡1(mod 2),j≠n)；

f(vm-1, jvm, j)=2(j≡1(mod 2),j≠n)；

f(vm, jvm, j+1)=2(j≡1(mod 2),j≠n;j=4,m-1)；f(v1,3v1,4)=2；

f(v1,5v2,5)=2；其余点和边均为1。

则各点的权重为:φ(vi, j)=9(i≡0(mod 2),j≡0(mod 2));

φ(vi, j)=10(i≡1(mod 2),i≠1,m,j≡1(mod 2),j≠1,n)；

φ(vi, j)=13(i=1,j=3,5,n;i=m,j=4,n-2)；

φ(vi, j)=14(i=m,j≡1(mod 2),j≠n,i≡1(mod 2),i≠1,j=1)；φ(v1,1)=15。

因此，fgndi∑(Cm×Cn)≤2又fgndi∑(Cm×Cn)≥2，即证fgndi∑(Cm×Cn)=2。

2 路、圈分别与完全图的笛卡尔乘积图

定理4fgndi∑(Km)=3。

证明由完全图Km的定义知，Km的一个邻点全和可区别全染色实则为一个邻和可区别边染色。若Km只用2种颜色处理，不妨将点都染1，一个点对剩下(m-1)个点有(m-1)条连边，则每个点的关联边染2的个数范围只可能为[0,m-1]，若存在(m-1)条关联边都染2的点u，一定存在(m-1)条关联边全染1的点v，由于u,v相邻，故不存在上述情形，即Km无法用2种颜色来区分。φ(Km)表示完全图Km中各点权重的集合。若Km只用2种颜色染色，同时达到权重相同的点只有2个，染色情况如下：

情形1.m≡0(mod 2)。