星與星的聯圖點可區別I-全染色和點可區別VI-全染色

康慧君，陳祥恩

(西北師范大學 數學與統計學院，甘肅蘭州 730070)

1 準備工作

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

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

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

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

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

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

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

對于一個簡單圖G，用ni表示度是i的頂點的個數，δ≤i≤Δ，假設

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

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

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

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

引理2[14]

引理3[14]若圖G只有一個最大度頂點，且則

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

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

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

命題1ξ(G)≤

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

關于星與星的聯圖，有如下定義：

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的點有m個；

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

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

2 主要結果

定理1 設Sm∨Sn是星Sm和星Sn的聯,3≤m≤n≤n+2,且n=m,n=m+1，則

證明因為Δ(Sm∨Sn)=m+n+1,nΔ≥2由引理1可知，

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

分如下兩種情況考慮：

情況1m=n.

第一步：給連接ui與vj的邊進行染色，令

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

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

第二步：給兩個星的邊進行染色，令

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是字母顏色.

第三步：給點染色，令

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

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

上述染色是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}.

容易驗證f是I-全染色，接下來證明f是點可區別的.

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

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

證明每個C(ui)都包含除了i-1的所有數字顏色，i=1,2,…,m+1，因為起始點i是不同的，因此,C(u1),C(u2),…C(um+1)是互不相同的.

因為m=n，所以字母顏色α1,α2，…,αm剛好可以給兩邊星的邊染色，關聯邊用數字顏色，Sm和Sn的頂點至少用四種顏色染色，由此可見,m+n+2個點的色集合彼此不相同，從而得知上述I-全染色是點可區別的.

當m=n=3時，Sm∨Sn有2個7度(最大度)的點，由引理1知，只需給出(S3∨S3)的一個8點可區別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的邊進行染色，令

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∈{2,3,…,m+1}；

當j=n+1時，f(v1vn+1)=n-1.

第三步：給兩邊的點染色，令

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}，缺數字顏色n+2;

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

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

?

C(um+1)={m+1,m+2,…,n,n+1,n+2,1,…,m-1}，缺數字顏色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.

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

對于m+n-1個頂點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,根據事實1和事實2，C(u1),C(u2),…C(um+1)和C(v1),C(v2),…C(vn)是互不相同的，可區別的.

對于頂點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個點的色集合彼此互不相同，從而得知上述I-全染色是點可區別的.

當n=4,m=3時，S3∨S4有2個8度(最大度)的點，由引理1，則

假如S3∨S4存在9-點可區別全染色，使用的顏色為1,2，…，9.只需給出一個9-點可區別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個點的色集合彼此互不相同，從而是點可區別的.

定理2 設Sm∨Sn是星Sm與星Sn的聯，3≤m≤n≤n+2，且n=m+2，則

m+n+2≤

證明因為ΔSm∨Sn=m+n+1,m+n+2≤只需給出Sm∨Sn的一個(m+n+3)-點可區別I-全染色f.

第一步：給連接ui與vj的邊進行染色，令

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∈{2,3,…,m+1}，

因為n=m+2,所以Sn中的邊有兩條不能用字母顏色進行染色，必須用數字顏色來染色.

第三步：給點染色，令

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}，缺數字顏色n+2;

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

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

?

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

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

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

?

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

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

用上述染色給n=m+2的星進行染色，則發現Sn中的兩條邊v1vn和v1vn+1，v1vn+1可以用數字顏色n進行正常染色，v1vn無法正常染色.

當m=3，n=5時，

假如S3∨S5存在10-點可區別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)的補集的色集合沒有相同的顏色數，從而S5當中的邊v1v5不能正常染色，而邊v1v6可以用相同的顏色數5正常染色.

所以,對于n=m+2的情形，不存在10-點可區別I-全染色.

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

繼續取模長為n+2，則字母顏色為α1、α2、α3、α4，點ui與vj染其關聯邊的顏色，其中關聯邊用數字顏色染色，頂點用四種數字顏色染色，并且相鄰點著不同色，S3內部的聯邊u1u2、u1u3、u1u4分別用α1、α2、α3進行染色，S5內部的聯邊v1v2、v1v3、v1v4、v1v5、v1v6分別用α1、α2、α3、α4、α5進行染色.

最終得到的上述全染色是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個點的色集合彼此不相同，從而得知上述I-全染色是點可區別的.

當n=m+2時，現在只需證明Sm∨Sn有一個(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.

由此可以發現2n+4個點的色集合彼此不相同，從而上述I-全染色是點可區別的.

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

當m=n，n=m+1時，

當n=m+2時，ζ(Sm∨Sn)≤

3 討 論

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

當m=n，n=m+1時，

當n=m+2時，ζ(Sm∨Sn)≤

今后將繼續對n≥m+3的Sm∨Sn的點可區別I-全染色和點可區別VI-全染色做進一步的研究.