星與星的聯(lián)圖點(diǎn)可區(qū)別I-全染色和點(diǎn)可區(qū)別VI-全染色

康慧君，陳祥恩

(西北師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅蘭州 730070)

1 準(zhǔn)備工作

圖的點(diǎn)可區(qū)別正常邊染色的研究見文獻(xiàn)[1-7]，圖的點(diǎn)可區(qū)別一般邊染色的研究見文獻(xiàn)[8-9]，圖的點(diǎn)可區(qū)別正常全染色的研究見文獻(xiàn)[10-13]，圖的點(diǎn)可區(qū)別I-全染色和點(diǎn)可區(qū)別VI-全染色的研究見文獻(xiàn)[14-19].本文討論Sm與Sn的聯(lián)圖(3≤m≤n≤n+2)的點(diǎn)可區(qū)別I-和VI-全染色.

圖G的一個(gè)使用了k種顏色的一般全染色(k-一般全染色)是指一個(gè)映射f：V∨E→{1,2…,k}.

圖G的I-全染色，就是指對(duì)于這個(gè)圖G的一個(gè)一般全染色f，?u,v∈V,有f(u)≠f(v),?e1,e2∈E,一旦e1與e2相鄰，就有f(e1)≠f(e2).

圖G的VI-全染色，就是指對(duì)于圖G的一個(gè)一般全染色f，?e1,e2∈E，一旦e1與e2相鄰，就有f(e1)≠f(e2).

設(shè)f為圖G的k-點(diǎn)可區(qū)別I-全染色，若?u,v∈V(G),u≠v,有C(u)≠C(v)，稱f為圖G的k-點(diǎn)可區(qū)別I-全染色，記為k-VDITC，稱為圖G的點(diǎn)可區(qū)別I-全色數(shù)，記為即{k|G有k-VDVITC}.

同理，設(shè)f為G的k-點(diǎn)可區(qū)別VI-全染色，若?u,v∈V(G),u≠v,C(u)≠C(v)，稱f為圖G的k-點(diǎn)可區(qū)別VI-全染色，記為k-VDVITC，稱為圖G的點(diǎn)可區(qū)別VI-全色數(shù)，記為即{k|G有k-VDVITC}.

設(shè)G(V1,E1)與H(V2,E2)，且V1∩V2=?，E1∩E2=?,稱圖G∨H為G與H的聯(lián)，如果V(G∨H)=V1∪V2,E(G∨H)=E1∪E2∪{uv|u∈V1,v∈V2}.

對(duì)于一個(gè)簡(jiǎn)單圖G，用ni表示度是i的頂點(diǎn)的個(gè)數(shù)，δ≤i≤Δ，假設(shè)

δ≤i≤i+s≤Δ,s≥0}.

猜想1[14](VDITC猜想)或ξ(G)+1.

猜想2[14](VDVITC猜想)或ξ(G)+1.

引理1[14]對(duì)于任意圖G，如果存在兩個(gè)Δ(最大度)頂點(diǎn)，則

引理2[14]

引理3[14]若圖G只有一個(gè)最大度頂點(diǎn)，且則

引理4[14]如果存在正整數(shù)r，δ≤r≤Δ，且G沒有度為r的頂點(diǎn)，則

ni+s,δ≤i≤i+s≤r-1,s≥0;或

r+1≤i≤i+s≤Δ,s≥0}.

命題1ξ(G)≤

假設(shè)p∈Z，而q為正整數(shù)，用(p)q表示{1,2，…，q}中的模q同余于p的那個(gè)數(shù)，即(p)q∈{1,2，…，q}且(p)q≡p(modq).

關(guān)于星與星的聯(lián)圖，有如下定義：

V(Sm∨Sn)={u1,…,um+1,v1,…,vn+1}，E(Sm∨Sn)=

{u1u2,u1u3,…,u1um,u1um+1,v1v2,v1v3，

v1v4,…,v1vn+1}∪{uivj|i=1,2,…,m+1;

j=1,2,…,n+1}.

d(ui)=n+2,i=2,3,…,m+1，度為n+2的點(diǎn)有m個(gè)；

d(u1)=m+n+1，d(v1)=m+n+1，度為m+n+1的點(diǎn)有2個(gè)；

d(vj)=m+2,j=2,3,…,n+1，度為m+2的點(diǎn)有n個(gè).

2 主要結(jié)果

定理1 設(shè)Sm∨Sn是星Sm和星Sn的聯(lián),3≤m≤n≤n+2,且n=m,n=m+1，則

證明因?yàn)棣?Sm∨Sn)=m+n+1,nΔ≥2由引理1可知，

則需要給出Sm∨Sn的一個(gè)(m+n+2)的點(diǎn)可區(qū)別I-全染色f.

分如下兩種情況考慮：

情況1m=n.

第一步：給連接ui與vj的邊進(jìn)行染色，令

f(uivj)=(i+j-1)n+2，f(uivj)∈{1,2,…，

n+2}，1≤i≤m+1,1≤j≤n+1.

第二步：給兩個(gè)星的邊進(jìn)行染色，令

f(uiuj)=αj-1,i=1,j=2,3,…,m+1，f(vivj)=αj-1,i=1,j=2,3,…,n+1，其中,α1,α2，…,αm是字母顏色.

第三步：給點(diǎn)染色，令

f(ui)=α1,i=2,3,…,m+1，f(u1)=α2,f(vj)=α3,j=2,3,…,n+1,f(v1)=α4.

對(duì)Sm和Sn的點(diǎn)進(jìn)行染色時(shí)不要用{1，2，…，n+2}中的顏色，只用字母顏色染就夠了，且Sm中用兩種字母顏色，ui,i=2,3,…,m+1只用一種顏色染，對(duì)Sn用同樣的辦法進(jìn)行染色.

上述染色是I-全染色，并且在此染色下有:

C(u1)={1,2,…,n,n+1}；

C(u2)={2,3,…,n,n+1,n+2}；

C(u3)={3,…,n,n+1,n+2,1}；

C(u4)={4,…,n,n+1,n+2,1,2}；

?

C(um+1)={m+1,m+2,…,n,n+1,n+2,1,…,m-1}.

C(v1)={1,2,…,m,m+1}；

C(v2)={2,…,m,m+1,m+2}；

?

C(vn+1)={n+1,n+2,1,…,n-3}.

容易驗(yàn)證f是I-全染色，接下來證明f是點(diǎn)可區(qū)別的.

事實(shí)1：C(u1),C(u2),…C(um+1)是互不相同的色集合.

事實(shí)2：C(v1),C(v2),…C(vn+1)是互不相同的色集合.

證明每個(gè)C(ui)都包含除了i-1的所有數(shù)字顏色，i=1,2,…,m+1，因?yàn)槠鹗键c(diǎn)i是不同的，因此,C(u1),C(u2),…C(um+1)是互不相同的.

因?yàn)閙=n，所以字母顏色α1,α2，…,αm剛好可以給兩邊星的邊染色，關(guān)聯(lián)邊用數(shù)字顏色，Sm和Sn的頂點(diǎn)至少用四種顏色染色，由此可見,m+n+2個(gè)點(diǎn)的色集合彼此不相同，從而得知上述I-全染色是點(diǎn)可區(qū)別的.

當(dāng)m=n=3時(shí)，Sm∨Sn有2個(gè)7度(最大度)的點(diǎn)，由引理1知，只需給出(S3∨S3)的一個(gè)8點(diǎn)可區(qū)別I-全染色f，令

f(uivj)=i+j-1,i=1,2,3,4,j=1,2,3,4;

f(u1vj)=j,j=1,2,3,4；f(u2vj)=j+1,j=1,2,3,4；

f(u3vj)=j+2,j=1,2,3,4；f(u4vj)=j+3,j=1,2,3,4；

f(u1)=1,f(ui)=2,i=2,3,4；f(v1)=3,f(vj)=4,j=2,3,4；

f(u1u2)=6;f(u1u3)=7;f(u1u4)=8；f(v1v2)=6;f(v1v3)=7;f(v1v4)=8.

上述染色是I-全染色，并且在此染色下有

情況2n=m+1.

第一步：給連接ui與vj的邊進(jìn)行染色，令

f(uivj)=(i+j-1)n+2,f(uivj)∈{1,2,…,n+2},1≤i≤m+1,1≤j≤n+1.

第二步：給兩個(gè)星的邊進(jìn)行染色，令

f(u1ui)=αi-1,i∈{2,3,…,m+1}；f(v1vj)=αj-1,j∈{2,3,…,m+1}；

當(dāng)j=n+1時(shí)，f(v1vn+1)=n-1.

第三步：給兩邊的點(diǎn)染色，令

f(ui)=α1,i=2,3,…,m+1，f(u1)=α2,

f(vj)=α3,j=2,3,…,n+1,f(v1)=α4；

只用字母顏色染色，且只需四種字母顏色染色就夠了.

上述染色是I-全染色，并且在此染色下有:

C(u1)={1,2,…,n,n+1}，缺數(shù)字顏色n+2;

C(u2)={2,3,…,n,n+1,n+2}，缺數(shù)字顏色1；

C(u3)={3,…,n,n+1,n+2,1}，缺數(shù)字顏色2；

?

C(um+1)={m+1,m+2,…,n,n+1,n+2,1,…,m-1}，缺數(shù)字顏色m.

C(v1)={1,2,…,m,m+1}，缺顏色m+2，m+3，即n+1，n+2；

C(v2)={2,…,m,m+1,m+2}，缺顏色1，m+3;

?

C(vn+1)={n+1,n+2,1,…,n-3}，缺顏色n，n-1.

對(duì)于頂點(diǎn)u1和v1進(jìn)行染色，共包含2m+2種顏色，其中C(u1)≠C(v1).

對(duì)于m+n-1個(gè)頂點(diǎn)u2,u3,…,um+1和v2,v3…,vn+1,使得|C(ui)|=m+4,i=2,3,…,m+1,|C(vj)|=m+4,j=2,3,…,n,根據(jù)事實(shí)1和事實(shí)2，C(u1),C(u2),…C(um+1)和C(v1),C(v2),…C(vn)是互不相同的，可區(qū)別的.

對(duì)于頂點(diǎn)vn+1，色集合包含m+2種顏色，C(v1),C(vn+1)包含的顏色不同，因此，色集合C(v1)≠C(vn+1)，并且，C(u1)包含顏色1，但C(vn+1)不包含顏色1，所以C(u1)≠C(vn+1)，由此可見，C(u1)≠C(vn+1)≠C(v1).

由此可見,m+n+2個(gè)點(diǎn)的色集合彼此互不相同，從而得知上述I-全染色是點(diǎn)可區(qū)別的.

當(dāng)n=4,m=3時(shí)，S3∨S4有2個(gè)8度(最大度)的點(diǎn)，由引理1，則

假如S3∨S4存在9-點(diǎn)可區(qū)別全染色，使用的顏色為1,2，…，9.只需給出一個(gè)9-點(diǎn)可區(qū)別I-全染色即可，令

f(uivj)=i+j-1,i=1,2,3,4,j=1,2,3,4，5;

f(u1)=1,f(ui)=2,i=2,3,4；f(v1)=3,f(vj)=4,j=2,3,4,5；f(u1u2)=7;f(u1u3)=8;f(u1u4)=9；f(v1v2)=6;f(v1v3)=7;f(v1v4)=8;f(v1v5)=9.

由此可見,上述染色是I-全染色，并且9個(gè)點(diǎn)的色集合彼此互不相同，從而是點(diǎn)可區(qū)別的.

定理2 設(shè)Sm∨Sn是星Sm與星Sn的聯(lián)，3≤m≤n≤n+2，且n=m+2，則

m+n+2≤

證明因?yàn)棣m∨Sn=m+n+1,m+n+2≤只需給出Sm∨Sn的一個(gè)(m+n+3)-點(diǎn)可區(qū)別I-全染色f.

第一步：給連接ui與vj的邊進(jìn)行染色，令

f(uivj)=(i+j-1)n+2,f(uivj)∈{1,2,…,n+2},1≤i≤m+1,1≤j≤n+1.

第二步：給兩個(gè)星的邊進(jìn)行染色，令

f(u1ui)=αi-1,i∈{2,3,…,m+1}；

f(v1vj)=αj-1,j∈{2,3,…,m+1}，

因?yàn)閚=m+2,所以Sn中的邊有兩條不能用字母顏色進(jìn)行染色，必須用數(shù)字顏色來染色.

第三步：給點(diǎn)染色，令

f(ui)=α1,i=2,3,…,m+1，f(u1)=α2,

f(vj)=α3,j=2,3,…,n+1,f(v1)=α4.

上述染色是I-全染色，并且在此染色下有：

C(u1)={1,2,…,n,n+1}，缺數(shù)字顏色n+2;

C(u2)={2,3,…,n,n+1,n+2}，缺數(shù)字顏色1；

C(u3)={3,…,n,n+1,n+2,1}，缺數(shù)字顏色2；

?

C(um+1)={m+1,m+2,…,n,n+1,n+2,1,…,m-1}，缺數(shù)字顏色m；

C(v1)={1,2,…,m,m+1}，缺數(shù)字顏色m+2，m+3，m+4即n，n+1，n+2；

C(v2)={2,…,m,m+1,m+2}，缺數(shù)字顏色1，m+3，m+4即1，n+1，n+2；

?

C(vn)={n,n+1,n+2,1,2,…,n-4}，缺數(shù)字顏色n-1，n-2，n-3；

C(vn+1)={n+1,n+2,1,…,n-3}，缺數(shù)字顏色n，n-1，n-2；

用上述染色給n=m+2的星進(jìn)行染色，則發(fā)現(xiàn)Sn中的兩條邊v1vn和v1vn+1，v1vn+1可以用數(shù)字顏色n進(jìn)行正常染色，v1vn無法正常染色.

當(dāng)m=3，n=5時(shí)，

假如S3∨S5存在10-點(diǎn)可區(qū)別I-全染色，用上述方法給S3∨S5染色，令

f(uivj)=(i+j-1)n+2,f(uivj)∈{1,2,…,7},1≤i≤4,1≤j≤6；

由于

f(v1ui)={1,2,3,4},i=1,2,3,4；f(v5ui)={5,6,7,1},i=1,2,3,4；

可以看出，f(v1ui)和f(v5ui)的補(bǔ)集的色集合沒有相同的顏色數(shù)，從而S5當(dāng)中的邊v1v5不能正常染色，而邊v1v6可以用相同的顏色數(shù)5正常染色.

所以,對(duì)于n=m+2的情形，不存在10-點(diǎn)可區(qū)別I-全染色.

f(uivj)=(i+j-1)n+2,f(uivj)∈{1,2,…,7},1≤i≤4,1≤j≤6.

繼續(xù)取模長(zhǎng)為n+2，則字母顏色為α1、α2、α3、α4，點(diǎn)ui與vj染其關(guān)聯(lián)邊的顏色，其中關(guān)聯(lián)邊用數(shù)字顏色染色，頂點(diǎn)用四種數(shù)字顏色染色，并且相鄰點(diǎn)著不同色，S3內(nèi)部的聯(lián)邊u1u2、u1u3、u1u4分別用α1、α2、α3進(jìn)行染色，S5內(nèi)部的聯(lián)邊v1v2、v1v3、v1v4、v1v5、v1v6分別用α1、α2、α3、α4、α5進(jìn)行染色.

最終得到的上述全染色是I-全染色，并且在此染色下有：

C(u1)={1,2,3,4,5,6,α1,α2,α3}；C(u2)={2,3,4,5,6,7,α1}；

C(u3)={3,4,5,6,7,1,α2}；C(u4)={4,5,6,7,1,2,α3}；

C(v1)={1,2,3,4,α1,α2,α3}；C(v2)={2,3,4,5,α1}；

C(v3)={3,4,5,6,α2}；C(v4)={4,5,6,7,α3}；

C(v5)={5,6,7,1,α4}；C(v6)={6,7,1,2,5}.

由此可見，10個(gè)點(diǎn)的色集合彼此不相同，從而得知上述I-全染色是點(diǎn)可區(qū)別的.

當(dāng)n=m+2時(shí)，現(xiàn)在只需證明Sm∨Sn有一個(gè)(m+n+3)-VDITCf.令

f(uivj)=(i+j-1)n+2,f(uivj)∈{1,2,…,n+2},1≤i≤m+1,1≤j≤n+1；

f(u1ui)=αi-1，i=2,3,…,m+1，f(v1vj)=αj-1,j≠1,n+1；

f(v1vn+1)=n,j=n+1.

最終得到的上述全染色是I-全染色，并且在此染色下有:

C(u1)={1,2,…,n+1,α1,α2,…,αm}，i=1；

C(ui)={i,i+1,i+2,…,(i+n)n+2,αi-1}，i=2,…,m+1；

C(v1)={1,2,…,m+1,α1,α2,…,αm,αm+1}，j=1；

C(vj)={j,j+1,j+2,…,(j+m)n+2,αj-1}，j=1,2,…,n；

C(vn+1)={n+1,n+2,1,2,…,n-3,n}，j=n+1.

由此可以發(fā)現(xiàn)2n+4個(gè)點(diǎn)的色集合彼此不相同，從而上述I-全染色是點(diǎn)可區(qū)別的.

根據(jù)命題1，上述定理顯然是成立的，可以看出VDITC猜想以及VDVITC猜想對(duì)Sm∨Sn(3≤m≤n≤n+2)是成立的.

當(dāng)m=n，n=m+1時(shí)，

當(dāng)n=m+2時(shí)，ζ(Sm∨Sn)≤

3 討 論

本文研究了Sm∨Sn(3≤m≤n≤n+2)的點(diǎn)可區(qū)別I-全染色和點(diǎn)可區(qū)別VI-全染色，通過本文的討論，可以看出VDITC猜想及VDVITC猜想對(duì)Sm∨Sn(3≤m≤n≤n+2)是成立的，分類討論結(jié)果如下：

當(dāng)m=n，n=m+1時(shí)，

當(dāng)n=m+2時(shí)，ζ(Sm∨Sn)≤

今后將繼續(xù)對(duì)n≥m+3的Sm∨Sn的點(diǎn)可區(qū)別I-全染色和點(diǎn)可區(qū)別VI-全染色做進(jìn)一步的研究.