国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

K1,5,p和 K1,6,p的點(diǎn)可區(qū)別的IE-全染色及一般全染色

2018-09-10 09:56寇艷芳陳祥恩王治文
關(guān)鍵詞:子集中點(diǎn)情形

寇艷芳 ,陳祥恩 ,王治文

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

0 引 言

點(diǎn)可區(qū)別一般邊染色由HARARY等[1]于1985年提出,在文獻(xiàn)[1-6]中均有涉及.

近年來,點(diǎn)可區(qū)別的未必正常的全染色也得以研究.CHEN等[7]提出了點(diǎn)可區(qū)別IE-全染色,而LIU等[8]提出了一般點(diǎn)可區(qū)別全染色.

本文研究K1,5,p和K1,6,p的點(diǎn)可區(qū)別IE-全染色和一般點(diǎn)可區(qū)別全染色,并給出了其點(diǎn)可區(qū)別IE-全色數(shù)和一般點(diǎn)可區(qū)別全色數(shù).其完全三部圖Km,n,p的頂點(diǎn)集合為V=X∪Y∪Z,其中,X={x1,x2,…,xm},Y={y1,y2,…,yn},Z={z1,z2,…,zp},邊集合為{xiyj|i=1,2,…,m;j=1,2,…,n}∪{yjzt|j=1,2,…,n;t=1,2,…,p}∪{xizt|i=1,2,…,m;t=1,2,…,p},當(dāng)m=1時(shí),記X={x}.

約定文中圖的l-VDIETC或l-GVDTC所使用的l種顏色為1,2,…,l,令A(yù)l={1,2,…,l}.

1 準(zhǔn)備工作

一個(gè)圖的點(diǎn)可區(qū)別IE-全染色一定是點(diǎn)可區(qū)別一般全染色,因此下述命題成立.

下面給出K1,5,p的一個(gè)l-IE-全染色f.令f(x)=1,f(yj)=2,j=1,2,…,5;用maxD(zi)染點(diǎn)zi,i=1,2,…,p.而zi的關(guān)聯(lián)邊均染以i+5,i=1,2,…,l-5.對|D(zi)|=2,用min[D(x)∩D(zi)]染邊xzi,min[D(yj)∩D(zi)]染邊yjzi,j=1,2,…,5;對|D(zi)|=3,用min[D(x)∩D(zi)]染邊xzi,min[(D(yj)∩D(zi)){f(xzi)}]染邊yjzi,j=1,2,…,5;對|D(zi)|=4,用min[D(x)∩D(zi)]染邊xzi,min[(D(y1)∩D(zi)){f(xzi)}]染邊y1zi,min[(D(yj))∩D(zi){f(xzi),f(y1zi)}]染邊yjzi,j=2,3,4,5;對|D(zi)|=s(5≤s≤7),用min[D(x)∩D(zi)]染邊xzi,min[(D(y1)∩D(zi)){f(xzi)}]染邊y1zi,…,min[(D(yj)∩D(zi)){f(xzi),f(y1zi),…,f(yj-1zi)}]染邊yjzi,j=2,3,…,s-2;min[D(yj)∩D(zi)]染邊yjzi,j=s-1,s,…,5;min[D(x)∩D(yj)]染邊xyj,j=1,2,…,5.

最后得到K1,5,p的l-IE全染色f是點(diǎn)可區(qū)別的,因?yàn)閷?v∈V(K1,5,p),均有C(v)=D(v).

假設(shè){3},{4},…,{r-1}均為Z中點(diǎn)的色集合,那么{2,3,…,r-1}?C(yj),j=1,2,…,n,矛盾.不妨設(shè){3}為非Z中任意點(diǎn)的色集合,當(dāng)n=5時(shí),有以下2種情況:

(i) {4},{5},…,{r-1}中有一個(gè)非Z中任意點(diǎn)的色集合.不妨設(shè){4}為非Z中任意點(diǎn)的色集合,這樣{1},{2},{1,2},{3},{4}均非Z中點(diǎn)的色集合,那么除這5個(gè)子集外,Ar-1的其他1-子集,2-子集,…,7-子集均為Z中點(diǎn)的色集合,特別地,單元集{5},{6},…,{r-1}及{1,3},{1,4},{2,3},{2,4},{3,4}均為Z中點(diǎn)的色集合.那么{2,5,6,…,k-1}?C(yj)(j=1,2,…,5),且C(yj)含1,3,4中的至少某2種色.故每個(gè)C(yj)是Ar-1,Ar-1{1},Ar-1{3},Ar-1{4}之一,矛盾.

(ii) {4},{5},…,{r-1}均為Z中點(diǎn)的色集合.則{1,4,…,r-1}?C(x),{2,4,…,r-1}?C(yj)(j=1,2,…,5),這樣每個(gè)C(yj)為Ar-1,Ar-1{1},Ar-1{3},Ar-1{1,3}之一,矛盾.

當(dāng)n=6時(shí),有以下3種情況:

(i) 當(dāng){4},{5},…,{r-1}均為Z中點(diǎn)的色集時(shí),同上可推出矛盾.

下設(shè)k=5,在K1,6,19的5-GVDTC下,{1,2,3,4,5}的所有2-子集,3-子集,4-子集,5-子集恰好構(gòu)成K1,6,19的全體頂點(diǎn)的色集合.每個(gè)2-子集及其補(bǔ)集不屬于不同部的2個(gè)頂點(diǎn)的色集合,每個(gè)2-子集及其補(bǔ)集只能同時(shí)是Y中點(diǎn)的色集合或同時(shí)都是Z中點(diǎn)的色集合.當(dāng)然有某個(gè)2-子集是Z中點(diǎn)的色集合.不妨設(shè){1,2}∈{C(z)|z∈Z},那么{3,4},{3,5},{4,5}∈{C(z)|z∈Z},進(jìn)而{1,5},{2,5},{1,4},{2,4},{1,3},{2,3}∈{C(z)|z∈Z},從而10個(gè)2-子集及其補(bǔ)集都必須是Z中點(diǎn)的色集合,但Z中僅有19個(gè)頂點(diǎn),矛盾.

下面給出K1,6,p的一個(gè)l-IE-全染色f.令f(x)=1,f(yj)=2,j=1,2,…,6;用maxD(zi)染點(diǎn)zi,i=1,2,…,p.而zi的關(guān)聯(lián)邊均染以i+6,i=1,2,…,l-6.對|D(zi)|=2,用min[D(x)∩D(zi)]染邊xzi,min[D(yj)∩D(zi)]染邊yjzi,j=1,2,…,6;對|D(zi)|=3,用min[D(x)∩D(zi)]染邊xzi,min[(D(yj)∩D(zi)){f(xzi)}]染邊yjzi,j=1,2,…,6;對|D(zi)|=4,用min[D(x)∩D(zi)]染邊xzi,min[(D(y1)∩D(zi)){f(xzi)}]染邊y1zi,min[(D(yj)∩D(zi)){f(xzi),f(y1zi)}]染邊yjzi,j=2,3,…,6;對|D(zi)|=s′(5≤s′≤8),用min[D(x)∩D(zi)]染邊xzi,min[(D(y1)∩D(zi)){f(xzi)}]染邊y1zi,…,min[(D(yj)∩D(zi)){f(xzi),f(y1zi),…,f(yj-1zi)}]染邊yjzi,j=2,3,…,s′-2;min[D(yj)∩D(zi)]染邊yjzi,j=s′-1,s′,…,6;min[D(x)∩D(yj)]染邊xyj,j=1,2,…,6.

最后得到K1,6,p的l-IE全染色f是點(diǎn)可區(qū)別的,因?yàn)閷?v∈V(K1,6,p),均有C(v)=D(v).

2 主要結(jié)果及其證明

(ii)χgvt(K1,5,p)=

證明分以下幾種情形進(jìn)行討論:

下面給出K1,5,p的k-GVDTCf.令f(x)=f(yj)=k,j=1,2,…,5;用maxD(zi)染點(diǎn)zi,i=1,2,…,p.而zi的關(guān)聯(lián)邊均染以i+5,i=1,2,…,k-5.對|D(zi)|=2,用min[D(x)∩D(zi)]染邊xzi,min[D(yj)∩D(zi)]染邊yjzi,j=1,2,…,5;對|D(zi)|=3,用min[D(x)∩D(zi)]染邊xzi,用min[(D(yj)∩D(zi)){f(xzi)}]染邊yjzi,j=1,2,…,5;對|D(zi)|=4,用min[D(x)∩D(zi)]染邊xzi,用min[(D(y1)∩D(zi)){f(xzi)}]染邊y1zi,用min[(D(yj)∩D(zi)){f(xzi),f(y1zi)}]染邊yjzi,j=2,3,…,5;對|D(zi)|=q(5≤q≤7),用min[D(x)∩D(zi)]染邊xzi,用min[(D(y1)∩D(zi)){f(xzi)}]染邊y1zi,…,用min[(D(yj)∩D(zi)){f(xzi),f(y1zi),…,f(yj-1zi)}]染邊yjzi,j=2,3,…,q-2;用min[D(yj)∩D(zi)]染邊yjzi,j=q-1,q,…,5;用min[D(x)∩D(yj)]染邊xyj,j=1,2,…,5.

情形3當(dāng)p=496時(shí),在引理1(i)中令k=9,得K1,5,496無8-GVDTC.而K1,5,496的10-VDIETC可由引理2中的染色規(guī)則得到.

同時(shí)K1,5,495的9-VDIETC的構(gòu)造類似于引理2,不再詳述.

情形5K1,5,244無8-VDIETC.只要在引理3的證明過程中令r=9便可得.但其有9-VDIETC(可由K1,5,494的9-VDIETC限制在{x,y1,…,y5,z1,…,z244}上得到).同時(shí),在引理1(i)中令k=8,可知K1,5,244無7-GVDTC,其8-GVDTC可依照情形1構(gòu)造.

情形6117≤p≤243.先證K1,5,p無7-GVDTC.在引理1(ii)中令k=7,可知K1,5,117無7-GVDTC.但K1,5,p有8-VDIETC,K1,5,243的8-VDIETC的構(gòu)造類似于引理2.

情形7K1,5,116無7-VDIETC.只要在引理3的證明過程中令r=8便可得.但它有8-VDIETC,可通過將K1,5,243的8-VDIETC限制在{x,y1,…,y5,z1,…,z116}上得到.同時(shí),在引理1(ii)中令k=6,可知K1,5,116無6-GVDTC.而7-GVDTC可依照情形1構(gòu)造.

情形853≤p≤115.先證K1,5,p無6-GVDTC.在引理1(ii)中令k=6,可知K1,5,53無6-GVDTC.但K1,5,p有7-VDIETC,K1,5,115的7-VDIETC的構(gòu)造類似于引理2.

情形9K1,5,52無6-VDIETC.只要在引理3的證明過程中令r=7便可得.但其有7-VDIETC,可通過將K1,5,115的7-VDIETC限制在{x,y1,…,y5,z1,…,z52}上得到.同時(shí),在引理1(ii)中令k=5,可知K1,5,52無5-GVDTC,有6-GVDTC,可依照情形1構(gòu)造.

情形1021≤p≤51.先證K1,5,p無5-GVDTC.在引理1(ii)中令k=5,可知K1,5,21無5-GVDTC.但K1,5,p有6-VDIETC,K1,5,51的6-VDIETC構(gòu)造類似于引理2.

情形11K1,5,20無5-VDIETC.只要在引理3的證明過程中令r=7便可得.但其有6-VDIETC,可通過將K1,5,51的6-VDIETC限制在{x,y1,…,y5,z1,…,z20}上得到.同時(shí),K1,5,20無4-GVDTC(否則,{1,2,3,4}的非空子集不能區(qū)分諸頂點(diǎn)),但有5-GVDTC,可依照情形1構(gòu)造.

(ii)χgvt(K1,6,p)=

證明分以下幾種情形討論:

下面給出K1,6,p的k-GVDTCf.令f(x)=f(yj)=k,j=1,2,…,6;用maxD(zi)染點(diǎn)zi,i=1,2,…,p.而zi的關(guān)聯(lián)邊均染以i+6,i=1,2,…,k-6.對|D(zi)|=2,用min[D(x)∩D(zi)]染邊xzi,用min[D(yj)∩D(zi)]染邊yjzi,j=1,2,…,6;對|D(zi)|=3,用min[D(x)∩D(zi)]染邊xzi,min[(D(yj)∩D(zi)){f(xzi)}]染邊yjzi,j=1,2,…,6;對|D(zi)|=4,用min[D(x)∩D(zi)]染邊xzi,用min[(D(y1)∩D(zi)){f(xzi)}]染邊y1zi,用min[(D(yj)∩D(zi)){f(xzi),f(y1zi)}]染邊yjzi,j=2,3,…,6;對|D(zi)|=q′(5≤q′≤8),用min[D(x)∩D(zi)]染邊xzi,用min[(D(y1)∩D(zi)){f(xzi)}]染邊y1zi,…,用min[(D(yj)∩D(zi)){f(xzi),f(y1zi),…,f(yj-1zi)}]染邊yjzi,j=2,3,…,q′-2;用min[D(yj)∩D(zi)]染邊yjzi,j=q′-1,q,…,6;用min[D(x)∩D(yj)]染邊xyj,j=1,2,…,6.

情形2當(dāng)p=1 006時(shí),在引理4(i)中令k=10,得K1,6,504無9-GVDTC,那么K1,6,1 006無9-GVDTC.

而K1,6,p有10-VDIETC,其染色類似于引理5,不再贅述.

情形4K1,6,498無9-VDIETC.只要在引理3的證明過程中令r=10便可得.但其有10-VDIETC,可通過將K1,6,1 005的10-VDIETC限制在{x,y1,…,y6,z1,…,z498}上得到.同時(shí),在引理4(ii)中令k=8,可知K1,6,498無8-GVDTC,有9-GVDTC,可依照情形1構(gòu)造.

情形5當(dāng)243≤p≤497時(shí),先證K1,6,p無8-GVDTC.在引理4(ii)中令k=8,可知K1,5,243無8-GVDTC.但K1,6,p有9-VDIETC,K1,6,497的9-VDIETC構(gòu)造類似于引理5.

情形6K1,6,242無8-VDIETC.只要在引理3的證明過程中令r=9則可得.但其有9-VDIETC,可通過將K1,6,497的9-VDIETC限制在{x,y1,…,y6,z1,…,z242}上得到.同時(shí),在引理4(ii)中令k=7,可知K1,6,242無7-GVDTC,有8-GVDTC,可依照情形1構(gòu)造.

情形7當(dāng)115≤p≤241時(shí),先證K1,6,p無7-GVDTC.在引理4(ii)中令k=7,可知K1,6,115無7-GVDTC.但K1,6,p有8-VDIETC,K1,6,241的8-VDIETC構(gòu)造類似于引理5.

情形8K1,6,114無7-VDIETC.只要在引理3的證明過程中令r=8便可得.但其有8-VDIETC,可通過將K1,6,241的8-VDIETC限制在{x,y1,…,y6,z1,…,z114}上得到.同時(shí),在引理4(ii)中令k=6,可知K1,6,114無6-GVDTC,有7-GVDTC,可依照情形1構(gòu)造.

情形9當(dāng)51≤p≤113時(shí),在引理4(ii)中令k=6,可知K1,6,51無6-GVDTC.但K1,6,p有7-VDIETC,K1,6,113的7-VDIETC構(gòu)造類似于引理5.

情形10K1,6,50無6-VDIETC.只要在引理3的證明過程中令r=7便可得.但其有7-VDIETC,可通過將K1,6,113的7-VDIETC限制在{x,y1,…,y6,z1,…,z50}上得到.同時(shí),在引理4(ii)中令k=5,可知K1,6,50無5-GVDTC,有6-GVDTC,可依照情形1構(gòu)造.

情形11當(dāng)19≤p≤49時(shí),在引理4(ii)中令k=5,可知K1,6,19無5-GVDTC.但K1,6,p有6-VDIETC,K1,6,49的6-VDIETC構(gòu)造類似于引理5.

情形12當(dāng)p=18時(shí),K1,6,18無5-VDIETC.只要在引理3的證明過程中令r=6便可得.但其有6-VDIETC,可通過將K1,6,49的6-VDIETC限制在{x,y1,…,y6,z1,…,z18}上得到.同時(shí)易證K1,6,18無4-GVDTC,而有5-GVDTC.將{1,2,…,5}的所有5-子集,4-子集,3-子集,2-子集依次分配給X,Y,Z中點(diǎn)的色集合,可得其染色(25-1-5>p+7).

對于一般的完全三部圖的VDIETC與GVDTC,筆者正在進(jìn)一步探索中.

猜你喜歡
子集中點(diǎn)情形
拓?fù)淇臻g中緊致子集的性質(zhì)研究
逾期清稅情形下納稅人復(fù)議權(quán)的行使
例談圓錐曲線中的中點(diǎn)和對稱問題
關(guān)于丟番圖方程x3+1=413y2*
Carmichael猜想的一個(gè)標(biāo)注
關(guān)于奇數(shù)階二元子集的分離序列
中點(diǎn)的聯(lián)想
探究一道課本習(xí)題的一般情形
從特殊走向一般
每一次愛情都只是愛情的子集