輪和扇三類聯(lián)圖的鄰點(diǎn)被擴(kuò)展和可區(qū)別全染色*

張輝，陳祥恩，王治文

(1. 西北師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 甘肅 蘭州 730070； 2. 寧夏大學(xué)數(shù)學(xué)統(tǒng)計(jì)學(xué)院, 寧夏 銀川 750021)

圖G的一個(gè)全k-染色是指k種顏色對(duì)圖G的全體頂點(diǎn)及邊的一個(gè)分配。

設(shè)c是圖G的一個(gè)全k-染色，任意的x∈V(G)，稱w(x)=∑exc(e)+∑y∈N(x)c(y)為點(diǎn)x的擴(kuò)展和，其中N(x)={y∈V(G)|xy∈E(G)}。稱圖G的全k-染色c為鄰點(diǎn)被擴(kuò)展和可區(qū)別(簡(jiǎn)記為NESD)，如果w(x)≠w(y)，其中xy∈E(G)。

使得圖G存在NESD全k-染色中k的最小值被稱為圖G的鄰點(diǎn)被擴(kuò)展和可區(qū)別全色數(shù)(neighbor expanded sum distinguishing index )，簡(jiǎn)記為egndiΣ(G)。

文[7]中給出輪和扇的概念，對(duì)n+1階輪Wn，設(shè)其頂點(diǎn)集合為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的聯(lián)圖G1∨G2是指在G1+G2中，把G1的每個(gè)頂點(diǎn)和G2的每個(gè)頂點(diǎn)連接起來所得到的圖。

文[9]中研究了路、圈、完全圖和樹等圖的鄰點(diǎn)被擴(kuò)展和可區(qū)別全染色，確定了它們的鄰點(diǎn)被擴(kuò)展和可區(qū)別全色數(shù)。并提出了一個(gè)猜想。文[10-12]對(duì)圖的點(diǎn)可區(qū)別全染色、奇優(yōu)美性及完美匹配計(jì)數(shù)給出相關(guān)結(jié)論。

命 題1[9]設(shè)Pm(m≥2)是m階的路，則

命題2[9]設(shè)Cm(m≥3)是m階的圈，則egndiΣ(Cm)=2。

命題3[9]設(shè)Kn(n≥2)是n階的完全圖，則egndiΣ(Kn)=2。

命題4[9]設(shè)T是n(n>2)階的樹，則egndiΣ(T)≤2。

猜想1[9]設(shè)G為簡(jiǎn)單圖，則egndiΣ(G)≤2。

1 主要結(jié)論及其證明

定理1 設(shè)m≥3,n≥3。則egndiΣ(Wm∨Wn)=2。

證明設(shè)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的一個(gè)全k-染色。顯然Wm∨Wn沒有NESD全1-染色，下面給出Wm∨Wn的一個(gè)NESD全2-染色。

情形1m,n均為偶數(shù)且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。則每個(gè)頂點(diǎn)的擴(kuò)展和計(jì)算如下：

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。故當(dāng)m,n均為偶數(shù)且m≠n時(shí)，c是Wm∨Wn的一個(gè)NESD全2-染色。

情形2m,n均為偶數(shù)且m=n

(i)m=n=4時(shí)。

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。則每個(gè)頂點(diǎn)的擴(kuò)展和計(jì)算如下：

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

顯然當(dāng)m,n均為偶數(shù)且m=n=4時(shí)，c是W4∨W4的一個(gè)NESD全2-染色。

(ii) 當(dāng)m=n≥6時(shí)。

顯然當(dāng)m,n均為偶數(shù)且m=n≥6時(shí)，c是Wm∨Wn的一個(gè)NESD全2-染色。

情形3m,n均為奇數(shù)且m≠n

(i) 當(dāng)m與n中恰好有一個(gè)等于3時(shí)。

不妨設(shè)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。則每個(gè)頂點(diǎn)的擴(kuò)展和計(jì)算如下：

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。故當(dāng)m,n均為奇數(shù)且m≠n(m=3)時(shí)，c是W3∨Wn的一個(gè)NESD全2-染色。

(ii) 當(dāng)m與n均大于3時(shí)。

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。除上述邊染顏色外，其余邊均染顏色。則每個(gè)頂點(diǎn)的擴(kuò)展和計(jì)算如下：

顯然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。故當(dāng)m,n均為奇數(shù)且m≠n(m>3,n>3)時(shí)，c是Wm∨Wn的一個(gè)NESD全2-染色。

情形4m,n均為奇數(shù)且m=n

(i)當(dāng)m=n=3時(shí)。

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。則每個(gè)頂點(diǎn)的擴(kuò)展和計(jì)算如下：

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

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

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

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

顯然當(dāng)m,n均為奇數(shù)且m=n=3時(shí)，c是W3∨W3的一個(gè)NESD全2-染色。

(ii)當(dāng)m=n≥5時(shí)。

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。則每個(gè)頂點(diǎn)的擴(kuò)展和計(jì)算如下：

顯然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。故當(dāng)m,n均為奇數(shù)且m=n≥5時(shí)，c是Wm∨Wn的一個(gè)NESD全2-染色。

情形5m是奇數(shù)，n是偶數(shù)且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。則每個(gè)頂點(diǎn)的擴(kuò)展和計(jì)算如下：

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。故當(dāng)m是奇數(shù)，n是偶數(shù)且m>n時(shí)，c是Wm∨Wn的一個(gè)NESD全2-染色。

情形6m是奇數(shù)，n是偶數(shù)且m

(i)當(dāng)m=3時(shí)。

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。則每個(gè)頂點(diǎn)的擴(kuò)展和計(jì)算如下：

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。故當(dāng)m是奇數(shù)，n是偶數(shù)且m

(ii)當(dāng)m≥5時(shí)。

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。則每個(gè)頂點(diǎn)的擴(kuò)展和計(jì)算如下：

顯然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。故當(dāng)m是奇數(shù)，n是偶數(shù)且m

注1 當(dāng)m是偶數(shù),n是奇數(shù)且m>n時(shí)，由輪與輪聯(lián)圖的對(duì)稱性可得，它與情形6相同。同理，當(dāng)m是偶數(shù),n是奇數(shù)且m

綜上可證egndi∑(Wm∨Wn)=2。

定理2設(shè)m≥3,n≥3。則egndiΣ(Fm∨Wn)=2。

證明設(shè)

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的一個(gè)全k-染色。顯然Fm∨Wn沒有NESD全1-染色，下面給出Fm∨Wn的一個(gè)NESD全2-染色。

情形1m,n均為偶數(shù)且m≠n，在定理1的情形1中刪去邊umu1后，就可得Fm∨Wn在m,n均為偶數(shù)且m≠n時(shí)的一個(gè)NESD全2-染色。

情形2m,n均為偶數(shù)且m=n，在定理1的情形2的(1)中刪去邊v3v4后，就可得F4∨W4的一個(gè)NESD全2-染色。在定理 1的情形2的(2)中刪去邊umu1后，就可得Fm∨Wn在m,n均為偶數(shù)且m=n≥6時(shí)的一個(gè)NESD全2-染色。

情形3m,n均為奇數(shù)且m≠n，在定理 1的情形3的(1)中刪去邊u1u2后，就可得F3∨Wn在m,n均為奇數(shù)且m≠n(m=3)時(shí)的一個(gè)NESD全2-染色。在定理 1的情形3的(2)中刪去邊u1u2后，就可得Fm∨Wn在m,n均為奇數(shù)且m≠n(m>3,n>3)時(shí)的一個(gè)NESD全2-染色。

情形4m,n均為奇數(shù)且m=n，在定理 1的情形4的(1)中刪去邊u1u3后，就可得F3∨W3的一個(gè)NESD全2-染色。在定理 1的情形4的(2)中刪去邊umu1后，就可得Fm∨Wn在m,n均為奇數(shù)且m=n≥5時(shí)的一個(gè)NESD全2-染色。

情形5m是奇數(shù),n是偶數(shù)且m>n，在定理 1的情形5中刪去邊u1u2后，就可得Fm∨Wn在m是奇數(shù)，n是偶數(shù)且m>n時(shí)的一個(gè)NESD全2-染色。

情形6m是奇數(shù),n是偶數(shù)且m

情形7m是偶數(shù),n是奇數(shù)且m>n，在定理 1的情形6的(1)中刪去邊vnv1后，就可得Fm∨W3在m是偶數(shù),n是奇數(shù)且m>n(n=3)時(shí)一個(gè)NESD全2-染色。在定理 1 的情形6的(2)中刪去邊vnv1后，就可得Fm∨Wn在m是偶數(shù),n是奇數(shù)且m>n≥5時(shí)的一個(gè)NESD全2-染色。

情形8m是偶數(shù),n是奇數(shù)且m

綜上可證egndiΣ(Fm∨Wn)=2。

定理3 設(shè)m≥3,n≥3,則egndiΣ(Fm∨Fn)=2。

證明設(shè)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的一個(gè)全k-染色。顯然Fm∨Fn沒有NESD全1-染色，下面給出Fm∨Fn的一個(gè)NESD全2-染色。

情形1m,n均為偶數(shù)且m≠n，在定理 1的情形1中刪去邊umu1與邊vnv1后，就可得Fm∨Fn在m,n均為偶數(shù)且m≠n時(shí)的一個(gè)NESD全2-染色。

情形2m,n均為偶數(shù)且m=n

(i)當(dāng)m=n=4時(shí)：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。則每個(gè)頂點(diǎn)的擴(kuò)展和計(jì)算如下：

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

顯然當(dāng)m,n均為偶數(shù)且m=n=4時(shí)，c是F4∨F4的一個(gè)NESD全2-染色。

w(v0)=5m+3;

顯然當(dāng)m,n均為偶數(shù)且m=n≥6時(shí)，c是Fm∨Fn的一個(gè)NESD全2-染色。

情形3m,n均為奇數(shù)且m≠n，在定理 1的情形3的(1)中刪去邊u1u2與邊vn-1vn后，就可得F3∨Fn在m,n均為奇數(shù)且m≠n(m=3)時(shí)的一個(gè)NESD全2-染色。在定理 1的情形3的(2)中刪去邊u1u2與邊v1v2后，就可得Fm∨Fn在m,n均為奇數(shù)且m≠n(m>3,n>3)時(shí)的一個(gè)NESD全2-染色。

情形4m,n均為奇數(shù)且m=n，在定理 1的情形4的(1)中刪去邊u1u3與邊v1v2后，就可得F3∨F3的一個(gè)NESD全2-染色。在定理 1的情形4的(2)中刪去邊u1u2與邊v2v3后，就可得Fm∨Fn在m,n均為奇數(shù)且m=n≥5時(shí)的一個(gè)NESD全2-染色。

情形5m是奇數(shù),n是偶數(shù)且m>n，在定理 1的情形5中刪去邊u1u2與邊v1v2后，就可得Fm∨Fn在m是奇數(shù),n是偶數(shù)m>n時(shí)的一個(gè)NESD全2-染色。

情形6m是奇數(shù),n是偶數(shù)且m

注2 當(dāng)m是偶數(shù),n是奇數(shù)且m>n時(shí)，由扇與扇聯(lián)圖的對(duì)稱性可得，它與情形6相同。同理，當(dāng)m是偶數(shù),n是奇數(shù)且m

綜上可證egndiΣ(Fm∨Fn)=2。

2 結(jié) 語(yǔ)

在本文中先探討了兩輪之聯(lián)的鄰點(diǎn)被擴(kuò)展和可區(qū)別全染色，并得到了它的鄰點(diǎn)被擴(kuò)展和可區(qū)別全色數(shù)。另外，通過刪邊的方法得到了扇與輪的聯(lián)與兩扇之聯(lián)的鄰點(diǎn)被擴(kuò)展和可區(qū)別全染色，并確定了它們的鄰點(diǎn)被擴(kuò)展和可區(qū)別全色數(shù)。那么這種方法是不是可以運(yùn)用到其它圖的聯(lián)圖上，進(jìn)而得到某些聯(lián)圖的鄰點(diǎn)被擴(kuò)展和可區(qū)別全染色及其鄰點(diǎn)被擴(kuò)展和可區(qū)別全色數(shù)，或者利用加邊的方法解決某些聯(lián)圖的鄰點(diǎn)被擴(kuò)展和可區(qū)別全染色及其鄰點(diǎn)被擴(kuò)展和可區(qū)別全色數(shù),這就是今后需要繼續(xù)研究的課題。