轮和扇三类联图的邻点被扩展和可区别全染色*

张辉，陈祥恩，王治文

(1. 西北师范大学数学与统计学院, 甘肃 兰州 730070； 2. 宁夏大学数学统计学院, 宁夏 银川 750021)

图G的一个全k-染色是指k种颜色对图G的全体顶点及边的一个分配。

设c是图G的一个全k-染色，任意的x∈V(G)，称w(x)=∑exc(e)+∑y∈N(x)c(y)为点x的扩展和，其中N(x)={y∈V(G)|xy∈E(G)}。称图G的全k-染色c为邻点被扩展和可区别(简记为NESD)，如果w(x)≠w(y)，其中xy∈E(G)。

使得图G存在NESD全k-染色中k的最小值被称为图G的邻点被扩展和可区别全色数(neighbor expanded sum distinguishing index )，简记为egndiΣ(G)。

文[7]中给出轮和扇的概念，对n+1阶轮Wn，设其顶点集合为V(Wn)={v0,v1,v2,,vn}，其边集合为E(Wn)={v0vi|i=1,2,,n}∪{vivi+1|i=1,2,n-1}∪{vnv1}。将n+1阶轮Wn的边vnv1删去之后得到的就是n+1阶的扇Fn。

文[8]中给出不相交的图G1和G2的联图G1∨G2是指在G1+G2中，把G1的每个顶点和G2的每个顶点连接起来所得到的图。

文[9]中研究了路、圈、完全图和树等图的邻点被扩展和可区别全染色，确定了它们的邻点被扩展和可区别全色数。并提出了一个猜想。文[10-12]对图的点可区别全染色、奇优美性及完美匹配计数给出相关结论。

命 题1[9]设Pm(m≥2)是m阶的路，则

命题2[9]设Cm(m≥3)是m阶的圈，则egndiΣ(Cm)=2。

命题3[9]设Kn(n≥2)是n阶的完全图，则egndiΣ(Kn)=2。

命题4[9]设T是n(n>2)阶的树，则egndiΣ(T)≤2。

猜想1[9]设G为简单图，则egndiΣ(G)≤2。

1 主要结论及其证明

定理1 设m≥3,n≥3。则egndiΣ(Wm∨Wn)=2。

证明设V(Wm)={u0,u1,u2,,um},E(Wm)={u0ui|i=1,2,,m}∪{uiui+1|i=1,2,,m-1}∪{umu1},V(Wn)={v0,v1,v2,,vn},E(Wn)={v0vj|j=1,2,,n}∪{vjvj+1|j=1,2,

n-1}∪{vnv1}。c是Wm∨Wn的一个全k-染色。显然Wm∨Wn没有NESD全1-染色，下面给出Wm∨Wn的一个NESD全2-染色。

情形1m,n均为偶数且m≠nc(u0)=2;c(u2i-1)=1,1≤2i-1≤m-1;c(u2i)=2,2≤2i≤m;c(v0)=1;c(v2j-1)=1，1≤2j-1≤n-1;c(v2j)=2, 2≤2j≤n;c(umu1)=c(vnv1)=c(u0v0)=2。除上述边染颜色2外(如图1所示)，其余边均染颜色1。则每个顶点的扩展和计算如下：

3≤2j-1≤n-1;

显然w(ui)≠w(ui+1),i=1,2,,m-1;w(um)≠w(u1);w(vj)≠w(vj+1),j=1,2,,n-1;w(vn)≠w(v1)。下面考虑w(u0)≠w(ui),1≤i≤m。

同理可得w(v0)≠w(vj),1≤j≤n,w(ui)≠w(vj),0≤i≤m,0≤j≤n。故当m,n均为偶数且m≠n时，c是Wm∨Wn的一个NESD全2-染色。

情形2m,n均为偶数且m=n

(i)m=n=4时。

c(u1)=c(u3)=c(v0)=c(v1)=c(v3)=1,c(u0)=c(u2)=c(u4)=c(v2)=c(v4)=2,c(u0ui)=2,1≤i≤4;c(uiui+1)=2,1≤i≤3;

图1 情形1的NESD全2-染色Fig.1 NESD total 2-coloring of case 1

c(u4u1)=c(v0v1)=c(v0v3)=c(v1v2)=c(v2v3)=2。除上述边染颜色2，其余边均染颜色1。则每个顶点的扩展和计算如下：

w(u0)=26;w(u1)=24;w(u2)=22;

w(u3)=24;w(u4)=22;

w(v0)=25;w(v1)=23;

w(v2)=21;w(v3)=23;w(v4)=19

显然当m,n均为偶数且m=n=4时，c是W4∨W4的一个NESD全2-染色。

(ii) 当m=n≥6时。

显然当m,n均为偶数且m=n≥6时，c是Wm∨Wn的一个NESD全2-染色。

情形3m,n均为奇数且m≠n

(i) 当m与n中恰好有一个等于3时。

不妨设m=3,c(u0)=c(u1)=c(u3)=2;c(u2)=1;c(v0)=1;c(v2j-1)=1,1≤2j-1≤n;c(v2j)=2,2≤2j≤n-1;c(u0ui)=2,1≤i≤3;c(u1u2)=c(u0v0)=c(v0v1)=c(v0v2)=c(v0vn)=c(vn-1vn)=2。除上述边染颜色2外，其余边均染颜色1。则每个顶点的扩展和计算如下：

w(v2)=18;w(v2j-1)=19,3≤2j-1≤n-2;

w(v2j)=17,4≤2j≤n-3;

w(vn-1)=18;w(vn)=20

显然w(ui)(i=0,1,2,3)之间互不相同，w(vj)≠w(vj+1),j=1,2,,n-1;w(vn)≠w(v1);w(v0)≠w(ui),i=0,1,2,3。下面考虑w(u0)≠w(vj),1≤j≤n。

同理可得w(v0)≠w(vj),1≤j≤n;w(ui)≠w(vj),1≤i≤m,1≤j≤n。故当m,n均为奇数且m≠n(m=3)时，c是W3∨Wn的一个NESD全2-染色。

(ii) 当m与n均大于3时。

c(u0)=2;c(u2i-1)=1;1≤2i-1≤m;c(u2i)=2;2≤2i≤m-1;c(v0)=1;c(v2j-1)=1,1≤2j-1≤n;c(v2j)=2,2≤2j≤n-1;c(u0um)=c(v0vn)=2。除上述边染颜色外，其余边均染颜色。则每个顶点的扩展和计算如下：

显然w(ui)≠w(ui+1),i=1,2,,m-1;w(um)≠w(u1);w(vj)≠w(vj+1),j=1,2,,n-1;w(vn)≠w(v1)。下面考虑w(u0)≠w(ui),1≤i≤m。

同理可得w(v0)≠w(vj),1≤j≤n;w(ui)≠w(vj),0≤i≤m,0≤j≤n。故当m,n均为奇数且m≠n(m>3,n>3)时，c是Wm∨Wn的一个NESD全2-染色。

情形4m,n均为奇数且m=n

(i)当m=n=3时。

c(u2)=c(v0)=c(v1)=c(v3)=1,c(u0)=c(u1)=c(u3)=c(v2)=2;c(u1v1)=c(u1v0)=c(u1v3)=c(u0v0)=c(u2v1)=c(u2v0)=c(u2v3)=c(v1v2)=c(v1v3)=2;c(v0vj)=2,1≤j≤3。除上述边染颜色2外，其余边均染颜色1。则每个顶点的扩展和计算如下：

w(u0)=18;w(u1)=20;

w(u2)=21;w(u3)=17;

w(v0)=24;w(v1)=23;

w(v2)=19;w(v3)=22

显然当m,n均为奇数且m=n=3时，c是W3∨W3的一个NESD全2-染色。

(ii)当m=n≥5时。

c(u0)=2;c(u2i-1)=1;1≤2i-1≤m;c(u2i)=2;2≤2i≤m-1;c(v0)=1;c(v2j-1)=1,1≤2j-1≤n;c(v2j)=2,2≤2j≤n-1;c(u2k-1u2k-1)=2,3≤2k-1≤m;c(u0um)=c(v0v1)=c(v0vn)=c(vnv1)=2;c(vjvj+1)=2,1≤j≤n-1。除上述边染颜色2外，其余边均染颜色1。则每个顶点的扩展和计算如下：

显然w(ui)≠w(ui+1),i=1,2,,m-1;w(um)≠w(u1);w(vj)≠w(vj+1),j=1,2,,n-1;w(vn)≠w(v1);w(u0)≠w(v0);w(ui)≠w(vj),0≤i≤m,0≤j≤n。下面考虑w(u0)≠w(ui),1≤i≤m。

同理可得w(v0)≠w(vj),1≤j≤n。故当m,n均为奇数且m=n≥5时，c是Wm∨Wn的一个NESD全2-染色。

情形5m是奇数，n是偶数且m>nc(u0)=2,c(u2i-1)=1,1≤2i-1≤m;c(u2i)=2,2≤2i≤m-1;c(v0)=1,c(v2j-1)=1,1≤2j-1≤n-1;c(v2j)=2,2≤2j≤n;c(um-1um)=c(vnv1)=2;c(v2kv2k+1)=2,2≤2k≤n-2。除上述边染颜色2外，其余边均染颜色1。则每个顶点的扩展和计算如下：

1≤2j-1≤n-1;

显然w(ui)≠w(ui+1),i=1,2,,m-1;w(um)≠w(u1);w(vj)≠w(vj+1),j=1,2,,n-1;w(vn)≠w(v1);w(u0)≠w(v0)。下面考虑w(u0)≠w(ui),1≤i≤m。

同理可得w(v0)≠w(vj),1≤j≤n;w(ui)≠w(vj),1≤i≤m,1≤j≤n。故当m是奇数，n是偶数且m>n时，c是Wm∨Wn的一个NESD全2-染色。

情形6m是奇数，n是偶数且m

(i)当m=3时。

c(u0)=c(u1)=c(u3)=2;c(u2)=1;c(v0)=1;c(v2j-1)=1,1≤2j-1≤n-1;c(v2j)=2,2≤2i≤n;c(u0u2)=c(u0v0)=c(u1v0)=c(u2v0)=2。除上述边染颜色2外，其余边均染颜色1。则每个顶点的扩展和计算如下：

w(v2j-1)=19, 1≤2j-1≤n-1;

w(v2j)=17， 2≤2j≤n

显然w(ui)(i=0,1,2,3)之间互不相同，w(vj)≠w(vj+1),j=1,2,,n-1;w(vn)≠w(v1);w(v0)≠w(ui),i=0,1,2,3。下面考虑w(u0)≠w(vj),1≤j≤n。

同理可得w(v0)≠w(vj),1≤j≤n;w(ui)≠w(vj),1≤i≤m,1≤j≤n。故当m是奇数，n是偶数且m

(ii)当m≥5时。

c(u0)=2,c(u2i-1)=1,1≤2i-1≤m;c(u2i)=2,2≤2i≤m-1;c(v0)=1;c(v2j-1)=1,1≤2j-1≤n-1;c(v2j)=2,2≤2j≤n;c(umu1)=2;c(uiui+1)=2,1≤i≤m-2。除上述边染颜色2外，其余边均染颜色1。则每个顶点的扩展和计算如下：

显然w(ui)≠w(ui+1),i=1,2,,m-1;w(um)≠w(u1);w(vj)≠w(vj+1),j=1,2,,n-1;w(vn)≠w(v1);w(u0)≠w(v0)。下面考虑w(u0)≠w(ui),1≤i≤m。

同理可得w(v0)≠w(vj),1≤j≤n;w(ui)≠w(vj),1≤i≤m,1≤j≤n。故当m是奇数，n是偶数且m

注1 当m是偶数,n是奇数且m>n时，由轮与轮联图的对称性可得，它与情形6相同。同理，当m是偶数,n是奇数且m

综上可证egndi∑(Wm∨Wn)=2。

定理2设m≥3,n≥3。则egndiΣ(Fm∨Wn)=2。

证明设

V(Fm)={u0,u1,u2,,um},

E(Fm)={u0ui|i=1,2,,m}∪{uiui+1|i=

1,2,,m-1},V(Wn)={v0,v1,v2,,vn},

E(Wn)={v0vj|j=1,2,,n}∪

{vjvj+1|j=1,2,,n-1}∪{vnv1}

c是Fm∨Wn的一个全k-染色。显然Fm∨Wn没有NESD全1-染色，下面给出Fm∨Wn的一个NESD全2-染色。

情形1m,n均为偶数且m≠n，在定理1的情形1中删去边umu1后，就可得Fm∨Wn在m,n均为偶数且m≠n时的一个NESD全2-染色。

情形2m,n均为偶数且m=n，在定理1的情形2的(1)中删去边v3v4后，就可得F4∨W4的一个NESD全2-染色。在定理 1的情形2的(2)中删去边umu1后，就可得Fm∨Wn在m,n均为偶数且m=n≥6时的一个NESD全2-染色。

情形3m,n均为奇数且m≠n，在定理 1的情形3的(1)中删去边u1u2后，就可得F3∨Wn在m,n均为奇数且m≠n(m=3)时的一个NESD全2-染色。在定理 1的情形3的(2)中删去边u1u2后，就可得Fm∨Wn在m,n均为奇数且m≠n(m>3,n>3)时的一个NESD全2-染色。

情形4m,n均为奇数且m=n，在定理 1的情形4的(1)中删去边u1u3后，就可得F3∨W3的一个NESD全2-染色。在定理 1的情形4的(2)中删去边umu1后，就可得Fm∨Wn在m,n均为奇数且m=n≥5时的一个NESD全2-染色。

情形5m是奇数,n是偶数且m>n，在定理 1的情形5中删去边u1u2后，就可得Fm∨Wn在m是奇数，n是偶数且m>n时的一个NESD全2-染色。

情形6m是奇数,n是偶数且m

情形7m是偶数,n是奇数且m>n，在定理 1的情形6的(1)中删去边vnv1后，就可得Fm∨W3在m是偶数,n是奇数且m>n(n=3)时一个NESD全2-染色。在定理 1 的情形6的(2)中删去边vnv1后，就可得Fm∨Wn在m是偶数,n是奇数且m>n≥5时的一个NESD全2-染色。

情形8m是偶数,n是奇数且m

综上可证egndiΣ(Fm∨Wn)=2。

定理3 设m≥3,n≥3,则egndiΣ(Fm∨Fn)=2。

证明设V(Fm)={u0,u1,u2,,um},E(Fm)={u0ui|i=1,2,,m}∪{uiui+1,|i=1,2,,m-1},V(Fn)={v0,v1,v2,,vn},E(Fn)={v0vj|j=1,2,,n}∪{vjvj+1|j=1,2,,n-1}。c是Fm∨Fn的一个全k-染色。显然Fm∨Fn没有NESD全1-染色，下面给出Fm∨Fn的一个NESD全2-染色。

情形1m,n均为偶数且m≠n，在定理 1的情形1中删去边umu1与边vnv1后，就可得Fm∨Fn在m,n均为偶数且m≠n时的一个NESD全2-染色。

情形2m,n均为偶数且m=n

(i)当m=n=4时：c(u1)=c(u3)=c(v0)=c(v1)=c(v3)=1,c(u0)=c(u2)=c(u4)=

c(v2)=c(v4)=2,c(u0ui)=2,1≤i≤4;c(uiui+1)=2,1≤i≤3;c(u4v4)=2。除上述边染颜色2外，其余边均染颜色1。则每个顶点的扩展和计算如下：

w(u0)=26;w(u1)=20;w(u2)=22；

w(u3)=24;w(u4)=20;

w(v0)=23；w(v1)=18；

w(v2)=19；

w(v3)=21；w(v4)=18

显然当m,n均为偶数且m=n=4时，c是F4∨F4的一个NESD全2-染色。

w(v0)=5m+3;

显然当m,n均为偶数且m=n≥6时，c是Fm∨Fn的一个NESD全2-染色。

情形3m,n均为奇数且m≠n，在定理 1的情形3的(1)中删去边u1u2与边vn-1vn后，就可得F3∨Fn在m,n均为奇数且m≠n(m=3)时的一个NESD全2-染色。在定理 1的情形3的(2)中删去边u1u2与边v1v2后，就可得Fm∨Fn在m,n均为奇数且m≠n(m>3,n>3)时的一个NESD全2-染色。

情形4m,n均为奇数且m=n，在定理 1的情形4的(1)中删去边u1u3与边v1v2后，就可得F3∨F3的一个NESD全2-染色。在定理 1的情形4的(2)中删去边u1u2与边v2v3后，就可得Fm∨Fn在m,n均为奇数且m=n≥5时的一个NESD全2-染色。

情形5m是奇数,n是偶数且m>n，在定理 1的情形5中删去边u1u2与边v1v2后，就可得Fm∨Fn在m是奇数,n是偶数m>n时的一个NESD全2-染色。

情形6m是奇数,n是偶数且m

注2 当m是偶数,n是奇数且m>n时，由扇与扇联图的对称性可得，它与情形6相同。同理，当m是偶数,n是奇数且m

综上可证egndiΣ(Fm∨Fn)=2。

2 结 语

在本文中先探讨了两轮之联的邻点被扩展和可区别全染色，并得到了它的邻点被扩展和可区别全色数。另外，通过删边的方法得到了扇与轮的联与两扇之联的邻点被扩展和可区别全染色，并确定了它们的邻点被扩展和可区别全色数。那么这种方法是不是可以运用到其它图的联图上，进而得到某些联图的邻点被扩展和可区别全染色及其邻点被扩展和可区别全色数，或者利用加边的方法解决某些联图的邻点被扩展和可区别全染色及其邻点被扩展和可区别全色数,这就是今后需要继续研究的课题。