兩圈之聯、路與圈的聯及兩路之聯的鄰點被擴展和可區別全染色

張 輝, 陳祥恩, 王治文

(1. 西北師范大學 數學與統計學院, 蘭州 730070; 2. 寧夏大學 數學統計學院, 銀川 750021)

1 引言與預備知識

關于圖的鄰和可區別一般邊染色的研究目前已有許多結果： 文獻[1]給出了圖的鄰和可區別一般邊染色; 文獻[2]給出了鄰和可區別一般全染色； 文獻[3]得出了若G是不含孤立邊的圖, 則圖G的鄰和可區別一般邊染色數不超過5； 文獻[4-6]提出了NSDTC猜想, 并驗證了該猜想對3-正則圖, 最大度不超過3的圖及不含4-階完全圖子式的圖等均成立； 文獻[7]在此基礎上提出了鄰點被擴展和可區別全染色, 研究了路、 圈、 完全圖、 樹等圖的鄰點被擴展和可區別全染色, 確定了其鄰點被擴展和可區別全色數, 并提出了一個猜想. 基于此, 本文考慮兩圈之聯、 路與圈的聯及兩路之聯的鄰點被擴展和可區別全染色.

圖G的一個全k-染色是指k種顏色對圖G的全體頂點及邊的一個分配. 設c是圖G的一個全k-染色, 對任意的x∈V(G), 稱

為點x的擴展和, 其中N(x)={y∈V(G)|xy∈E(G)}. 如果w(x)≠w(y), 則稱圖G的全k-染色c為鄰點被擴展和可區別(簡記為NESD), 其中xy∈E(G). 圖G的NESD全k-染色的最小值k稱為圖G的鄰點被擴展和可區別全色數, 簡記為egndi∑(G). 不相交的圖G1和G2的聯圖G1∨G2是指在G1+G2中, 將G1的每個頂點和G2的每個頂點連接起來得到的圖[8].

命題1[7]設Pm(m≥2)是m階的路, 則

命題2[7]設Cm(m≥3)是m階的圈, 則egndi∑(Cm)=2.

命題3[7]設Kn(n≥2)是n階的完全圖, 則egndi∑(Kn)=2.

命題4[7]設T是n(n≥2)階的樹, 則egndi∑(T)≤2.

猜想1(NESDTC猜想)[7]設G為簡單圖, 則egndi∑(G)≤2.

2 主要結果

定理1設m≥3,n≥3, 則egndi∑(Cm∨Cn)=2.

證明： 設Cm=x1x2…xmx1,Cn=y1y2…yny1,c是Cm∨Cn的一個全k-染色. 顯然Cm∨Cn沒有NESD全1-染色, 下面給出Cm∨Cn的一個NESD全2-染色.

情形1)m,n均為偶數且m≠n. 此時, 有

c(x2i-1)=1, 1≤2i-1≤m-1;c(x2i)=2, 2≤2i≤m;

c(y2j-1)=1, 1≤2j-1≤n-1;c(y2j)=2, 2≤2j≤n.

所有的邊均染顏色1, 則每個頂點的擴展和計算如下:

顯然

w(xi)≠w(xi+1),xixi+1∈E(G);w(yj)≠w(yj+1),yjyj+1∈E(G);

w(x1)≠w(xm);w(y1)≠w(yn).

情形2)m,n均為偶數且m=n. 此時, 有

c(x2i-1)=1, 1≤2i-1≤m-1;c(x2i)=2, 2≤2i≤m;c(y2j-1)=1, 1≤2j-1≤n-1;

c(y2j)=2, 2≤2j≤n;c(yjyj+1)=2, 1≤j≤n-1;

除上述3種邊染顏色2外, 其余邊均染顏色1, 則每個頂點的擴展和計算如下:

顯然

w(xi)≠w(xi+1),xixi+1∈E(G);w(x1)≠w(xm);w(yj)≠w(yj+1),

yjyj+1∈E(G);w(y1)≠w(ym);w(xi)≠w(yj), 1≤i≤m, 1≤j≤m.

故當m,n均為偶數且m=n時,c是Cm∨Cn的一個NESD全2-染色.

情形3)m,n均為奇數且m≠n. 此時, 有

c(x2i-1)=1, 1≤2i-1≤m;c(x2i)=2, 2≤2i≤m-1;c(y2j-1)=1, 1≤2j-1≤n;

c(y2j)=2, 2≤2j≤n-1;c(xm-1xm)=2;c(yn-1yn)=2.

除上述兩種邊染顏色2外, 其余邊均染顏色1, 則每個頂點的擴展和計算如下:

顯然

(1)

情形4)m,n均為奇數且m=n. 此時, 有下列3種子情形.

① 當m=n=3時,

c(x1)=c(x3)=c(y2)=1,c(x2)=c(y1)=c(y3)=2,

c(x1x3)=c(x1y2)=c(x3y2)=c(x3y3)=c(y1y2)=c(y2y3)=2.

除上述6條邊染顏色2外, 其余邊均染顏色1, 則每個頂點的擴展和計算如下:

w(x1)=15;w(x2)=12;w(x3)=16;w(y1)=13;w(y2)=17;w(y3)=14.

顯然當m,n均為奇數且m=n=3時,c是C3∨C3的一個NESD全2-染色.

② 當m=n=5時,

c(x3)=c(y1)=c(y3)=c(y5)=1.

除上述4個頂點染顏色1外, 其余頂點均染顏色2,

c(x3y1)=c(x4y2)=c(x5y5)=c(y2y3)=c(y3y4)=c(y4y5)=c(y1y5)=2.

除上述7條邊染顏色2外, 其余邊均染顏色1, 則每個頂點的擴展和計算如下:

w(x1)=18;w(x2)=17;w(x3)=19;w(x4)=18;w(x5)=19;

w(y1)=21;w(y2)=20;w(y3)=22;w(y4)=20;w(y5)=22.

顯然當m,n均為奇數且m=n=5時,c是C5∨C5的一個NESD全2-染色.

③ 當m=n≥7時,

c(x1)=c(xm)=2;c(x2i-1)=1, 3≤2i-1≤m-2;c(x2i)=2, 2≤2i≤m-1;

c(y2j-1)=1, 1≤2j-1≤n;c(y2j)=2, 2≤2j≤n-1;

c(x3y1)=c(x4y2)=c(xmyn)=c(y1yn)=2;c(yjyj+1)=2, 2≤j≤n-1.

除上述5種邊染顏色2外, 其余邊均染顏色1, 如圖1(A)所示, 則每個頂點的擴展和計算如下:

顯然當m,n均為奇數且m=n≥7時,c是Cm∨Cn的一個NESD全2-染色.

情形5)m是奇數、n是偶數且m>n. 此時, 有

c(x2i-1)=1, 1≤2i-1≤m;c(x2i)=2, 2≤2i≤m-1;

c(y2j-1)=1, 1≤2j-1≤n-1;c(y2j)=2, 2≤2j≤n;

c(x1xm)=c(x1y1)=c(y1yn)=2;c(yjyj+1)=2, 1≤j≤n-1.

除上述4種邊染顏色2外, 其余邊均染顏色1, 如圖1(B)所示, 則每個頂點的擴展和計算如下:

顯然有式(1).

情形6)m是奇數、n是偶數且m

c(x2i-1)=1, 1≤2i-1≤m;c(x2i)=2, 2≤2i≤m-1;

c(y2j-1)=1, 1≤2j-1≤n-1;c(y2j)=2, 2≤2j≤n;

c(x1xm)=c(x1y1)=c(y1yn)=2;c(xixi+1)=2, 1≤i≤m-1.

除上述4種邊染顏色2外, 其余邊均染顏色1, 如圖1(C)所示, 則每個頂點的擴展和計算如下:

顯然有式(1).

圖1 不同情形下的NESD全2-染色Fig.1 NESD total 2-coloring under different cases

當m是偶數、n是奇數且m>n時, 由圈與圈聯圖的對稱性可知, 此時與情形6)相同. 同理, 當m是偶數、n是奇數且m

綜上可證egndi∑(Cm∨Cn)=2.

定理2設m≥2,n≥3, 則egndi∑(Pm∨Cn)=2.

證明： 設Pm=x1x2…xm,Cn=y1y2…yny1,c是Pm∨Cn的一個全k-染色. 顯然Pm∨Cn沒有NESD全1-染色, 下面給出Pm∨Cn的一個NESD全2-染色.

情形1)m,n均為偶數且m≠n. 在定理1的情形1)中刪去邊x1xm后, 即可得Pm∨Cn在m,n均為偶數且m≠n時的一個NESD全2-染色.

情形2)m,n均為偶數且m=n. 在定理1的情形2)中刪去邊x1xm后, 即可得Pm∨Cn在m,n均為偶數且m=n時的一個NESD全2-染色.

情形3)m,n均為奇數且m≠n. 在定理1的情形3)中刪去邊x1xm后, 即可得Pm∨Cn在m,n均為奇數且m≠n時的一個NESD全2-染色.

情形4)m,n均為奇數且m=n.

① 當m=n=3時, 在定理1情形4)的①中刪去邊y1y3后, 即可得P3∨C3的一個NESD全2-染色;

② 當m=n=5時, 在定理1情形4)的②中刪去邊x1x5后, 即可得P5∨C5的一個NESD全2-染色;

③ 當m=n≥7時, 在定理1情形4)的③中刪去邊x1xm后, 即可得Pm∨Cn在m,n均為奇數且m=n≥7時的一個NESD全2-染色.

情形5)m是奇數、n是偶數且m>n. 在定理1的情形5)中刪去邊x1x2后, 即可得Pm∨Cn在m是奇數、n是偶數且m>n時的一個NESD全2-染色.

情形6)m是奇數、n是偶數且m

c(x2i-1)=1, 1≤2i-1≤m;c(x2i)=2, 2≤2i≤m-1;

c(y2j-1)=1, 1≤2j-1≤n-1;c(y2j)=2, 2≤2j≤n;c(xixi+1)=2, 1≤i≤m-1;

c(xtyt)=2, 1≤t≤m;c(yjyj+1)=2, 1≤j≤m;c(y1yn)=2.

除上述4種邊染顏色2外, 其余邊均染顏色1, 則每個頂點的擴展和計算如下:

顯然

w(xi)≠w(xi+1),xixi+1∈E(G);w(yj)≠w(yj+1),yjyj+1∈E(G);w(y1)≠w(yn).

情形7)m是偶數、n是奇數且m>n. 在定理1的情形6)中刪去邊yn-1yn后, 即可得Pm∨Cn在m是偶數、n是奇數且m>n時的一個NESD全2-染色.

情形8)m是偶數、n是奇數且m

綜上可證egndi∑(Pm∨Cn)=2.

定理3設m≥2,n≥2, 則egndi∑(Pm∨Pn)=2.

證明： 設Pm=x1x2…xm,Pn=y1y2…yn,c是Pm∨Pn的一個全k-染色. 顯然Pm∨Pn沒有NESD全1-染色. 下面給出Pm∨Pn的一個NESD全2-染色.

情形1)m,n均為偶數且m≠n. 在定理1的情形1)中刪去邊x1xm和邊y1yn后, 即可得Pm∨Pn在m,n均為偶數且m≠n時的一個NESD全2-染色.

情形2)m,n均為偶數且m=n. 在定理1的情形2)中刪去邊x1xm和邊y1yn后, 即可得Pm∨Pn在m,n均為偶數且m=n時的一個NESD全2-染色.

情形3)m,n均為奇數且m≠n. 在定理1的情形3)中刪去邊x1xm和邊y1yn后, 即可得Pm∨Pn在m,n均為奇數且m≠n時的一個NESD全2-染色.

情形4)m,n均為奇數且m=n. 此時, 有

c(x2i-1)=1, 1≤2i-1≤m;c(x2i)=2, 2≤2i≤m;c(y2j-1)=1, 1≤2j-1≤n;

c(y2j)=2, 2≤2j≤n;c(yjyj+1)=2, 1≤j≤n-1;c(x2ky2k)=2, 2≤2k≤m.

除上述兩種邊染顏色2外, 其余邊均染顏色1, 則每個頂點的擴展和計算如下:

顯然

w(xi)≠w(xi+1),xixi+1∈E(G);w(yj)≠w(yj+1),yjyj+1∈E(G);

w(xi)≠w(yj), 1≤i≤m, 1≤j≤n.

故當m,n均為奇數且m=n時,c是Pm∨Pn的一個NESD全2-染色.

情形5)m是奇數、n是偶數且m>n. 在定理1的情形5)中刪去邊x1x2和邊y1yn后, 即可得Pm∨Pn在m是奇數、n是偶數且m>n時的一個NESD全2-染色.

情形6)m是奇數、n是偶數且m

當m是偶數、n是奇數且m>n時, 由路與路聯圖的對稱性可知, 此時與情形6)相同. 同理, 當m是偶數、n是奇數且m

綜上可證egndi∑(Pm∨Pn)=2.

綜上所述, 本文首先討論了兩圈之聯的鄰點被擴展和可區別全染色, 得到了其鄰點被擴展和可區別全色數. 然后通過刪邊的方法得到了路與圈的聯及兩路之聯的鄰點被擴展和可區別全染色, 并確定了其鄰點被擴展和可區別全色數.