完全二部圖K8,n(8≤n≤34)的點(diǎn)可區(qū)別E-全染色

楊 瀾,陳祥恩

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

§1 引言

關(guān)于圖的點(diǎn)可區(qū)別一般邊染色已進(jìn)行了許多研究(如[1-4]).圖G的一個(gè)E-全染色φ是指使相鄰點(diǎn)著以不同色且每條關(guān)聯(lián)邊與它的端點(diǎn)著以不同的色的全染色.用C(x)表示在φ的作用下點(diǎn)x的顏色以及與x關(guān)聯(lián)的邊的色所構(gòu)成的集合(非多重集合).設(shè)φ為G的一個(gè)E-全染色,若?u,v ∈V(G),u≠v,有C(u)≠C(v),則φ稱為圖G的點(diǎn)可區(qū)別E-全染色(Vertex-Distinguishing E-Total Coloring),簡(jiǎn)稱為VDET染色.令存在k?VDET染色}.稱為圖G的點(diǎn)可區(qū)別E-全色數(shù).

文[5]中探討了完全圖,完全二部圖K2,n,星,輪,扇,路和圈的VDET染色.文[6]中得出了m個(gè)三階圈的聯(lián)圖和m個(gè)四階圈的聯(lián)圖的VDET色數(shù).文[7-9]中討論了完全二部圖K3,n,K4,n,K5,n的VDET染色,文[10-11]中部分討論了完全二部圖K7,n的VDET染色.本文主要討論了K8,n(8≤n ≤34)的VDET染色并且得到了K8,n的VDET色數(shù).

在本文中,對(duì)于完全二部圖K8,n,令V(K8,n)=X ∪Y,E(K8,n)={uivj:1≤i ≤8,1≤j ≤n},其中X={u1,u2,···,u8},Y={v1,v2,···,vn}.

給定K8,n的一個(gè)點(diǎn)可區(qū)別E-全染色φ,令

給定一個(gè)正整數(shù)k,{1,2,···,k}的i-子集是指{1,2,···,k}的包含i個(gè)元素的集合.

給定一個(gè)正整數(shù)l,一個(gè)集合M,|M|=l是指集合M中包含l個(gè)元素.

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

定理1當(dāng)8≤n ≤34時(shí),有(K8,n)=6.

證先證K8,n不存在5-VDET染色.設(shè)K8,n有一個(gè)5-VDET染色φ,顏色分別為1,2,3,4,5.考慮以下4種情形.

情形1|{φ(ui)|i=1,2,···,8}|=1.

此時(shí)A1中至少有3個(gè)成員都屬于C(Y),可知:在2,3,4,5中至少有一種色同時(shí)包含在每個(gè)C(ui)中,不妨設(shè)2∈C(ui),i=1,2,···,8,則每個(gè)C(ui)只可能是以下8個(gè)集合之一:{1,2},{1,2,3},{1,2,4},{1,2,5},{1,2,3,4},{1,2,3,5},{1,2,4,5},{1,2,3,4,5}.又因?yàn)閧3,4},{3,5},{4,5},{3,4,5}這三個(gè)集合中至少有一個(gè)屬于C(Y),則{1,2}一定不屬于C(X),7個(gè)集合不能區(qū)分X中的8個(gè)頂點(diǎn),矛盾.

情形2|{φ(ui)|i=1,2,···,8}|=2.

是{1,2,3,4,5}的4-子集,5-子集以及不在中的3-子集構(gòu)成的集合.

情形2.1中的成員均不屬于C(Y),顯然也不屬于C(X).

情形2.1.1Y中任一頂點(diǎn)的色集合不含中的成員.

事實(shí)1(i)中包含i的成員有8個(gè),i=1,2;

事實(shí)2以下陳述中至多有一句是正確的.

(i){1,2}屬于C(X);

(ii){1,3}或{2,3}屬于C(X);

(iii){1,4}或{2,4}屬于C(X);

(iv){1,5}或{2,5}屬于C(X).

事實(shí)2的 證明假如(i)-(iv)中至少有兩條是正確的,鑒于(ii),(iii),(iv)的地位是等價(jià)的,故只考慮以下兩種情況.若(i)和(ii)正確,此時(shí)C(Y)中的每個(gè)成員同時(shí)包含1,3(或2,3),由事實(shí)1(iv)知,只有6個(gè)集合可以作為C(X)中的成員,矛盾;若(ii)和(iii)正確,此時(shí)C(Y)中的每個(gè)成員同時(shí)包含3,4,由事實(shí)1(v)知,只有7個(gè)集合可以作為C(X)中的成員,矛盾.事實(shí)2證畢.

事實(shí)3出現(xiàn)在事實(shí)2中的四條陳述都不正確.

事實(shí)3的證明假如(i)成立,由1和2的對(duì)稱性,不妨設(shè)其頂點(diǎn)顏色為2,則每個(gè)C(vj)包含顏色1,故C(X)∪C(Y)1,2}}{{3,4,5}},其中1,2}}{{3,4,5}}包含16個(gè)成員.再由C(Y)中的成員均不是中的,也不是{1,2},且每個(gè)C(vj)均包含顏色1,可知:C(Y)?{{1,3,4},{1,3,5},{1,4,5},{1,2,3,4},{1,2,3,5},{1,2,4,5},{1,3,4, 5},{1,2,3,4,5}},故C(X)?{{1,2},{1,2,3},{1,2,4},{1,2,5},{2, 3, 4},{2, 3, 5},{2, 4, 5},{2,3, 4, 5}}.現(xiàn)由{1,4,5}屬于C(Y),若其頂點(diǎn)顏色為4,則{2,3,4}不能與之染色成功,矛盾;若其頂點(diǎn)顏色為5,則{2,3,5}不能與之染色成功,矛盾.因此(i)不成立.

假如(ii)成立,則C(Y)的每個(gè)成員均包含顏色3.由假設(shè)及事實(shí)1(ii)知,C(Y)只可能是中10個(gè)含3的成員.此時(shí)考慮8≤n ≤10的情況,可知C(X)∪C(Y)1,3},{2,3}},其中1,3},{2,3}}包含18個(gè)成員.此時(shí)以下兩個(gè)斷言是正確的.

斷言1{1,3,4}和{1,3,5}至多有一個(gè)屬于C(Y).

斷言1的證明假如{1,3,4}和{1,3,5}均屬于C(Y),由于{1,3}或{2,3}屬于C(X),其頂點(diǎn)顏色為1或2,其關(guān)聯(lián)邊顏色為3,故{1,3,4}和{1,3,5}的頂點(diǎn)顏色只能是4和5,其關(guān)聯(lián)邊的顏色只能是1或3.于是{1,4,5}和{2,4,5}均不屬于C(X).再由C(Y)中的每個(gè)成員均包含顏色3,則{1,4,5}和{2,4,5}均不屬于C(Y),此時(shí)

其中1,3},{2,3}}{{1,4,5},{2,4,5}}包含16個(gè)成員.下面考慮n=8的情況.由于C(X)中的每個(gè)成員均包含1或2,故{3,4,5}屬于C(Y),且其頂點(diǎn)顏色不是3.若其頂點(diǎn)顏色為4,則{1,2,4}不能與之染色成功,矛盾;若其頂點(diǎn)顏色為5,則{1,2,5}不能與之染色成功,矛盾.斷言1證畢.

斷言2{2,3,4}和{2,3,5}至多有一個(gè)屬于C(Y).

斷言2的證明與斷言1類似,此處不再贅述.

根據(jù)斷言1和斷言2,由對(duì)稱性,可不妨設(shè){1,3,4}和{2,3,5}屬于C(Y),其頂點(diǎn)顏色分別為4和5,則{1,4,5},{2,4,5}和{1,2,4,5}均不屬于C(X),否則與E-全染色矛盾,并且{1,4,5},{2,4,5}和{1,2,4,5}也不屬于C(Y).此時(shí)

15個(gè)集合不能區(qū)分X和Y中的至少16個(gè)頂點(diǎn),矛盾.因此(ii)不成立.

至于(iii)或(iv)可類似(ii)推出矛盾.

至此,事實(shí)3證畢.

以上事實(shí)說(shuō)明:含1或2的2-子集均不屬于C(X),從而C(X)∪C(Y)?B2∪B3,B2∪B3恰好包含16個(gè)集合.由前面的推理知:{3,4,5}屬于C(Y),中的成員都屬于C(X).若{3,4,5}的頂點(diǎn)顏色為3,則與{1,2,3}染色不成功,矛盾;若{3,4,5}的頂點(diǎn)顏色為4,則與{1,2,4}染色不成功,矛盾;若{3,4,5}的頂點(diǎn)顏色為5,則與{1,2,5}染色不成功,矛盾.

情形2.1.2中至少有一個(gè)成員屬于C(Y).

不妨設(shè)為{1,2,3},則C(X)中的每個(gè)成員將同時(shí)包含顏色1和顏色2,因此只有以下7個(gè)集合可以作為X中的頂點(diǎn)的色集合：{1,2},{1,2,4},{1,2,5},{1,2,3,4},{1,2,3,5},{1,2,4,5},{1,2,3,4,5},7個(gè)集合不能區(qū)分X中的8個(gè)頂點(diǎn),矛盾.

情形2.2中至少有一個(gè)成員屬于C(Y).

此時(shí)每個(gè)C(ui),i=1,2,···,8至少同時(shí)包含3,4,5中的某一種色,不妨設(shè)3∈C(ui),i=1,2,···,8.

情形2.2.1中的成員均不屬于C(Y),顯然{1,2,4}和{1,2,5}不是X和Y中任一頂點(diǎn)的色集合.下面分情況討論.

(i){1,3}和{2,3}中至少有一個(gè)屬于C(X).

此時(shí)C(Y)中的每個(gè)成員都包含顏色3,從而C(X)和C(Y)中的每個(gè)成員都包含顏色3,因此C(X)∪C(Y)1,3},{2,3}}{{4,5},{1,2,4},{1,2,5},{1,4,5},{2,4,5},{1,2,4,5}},即8+n ≤19+2?6=15,15個(gè)集合不能區(qū)分X和Y中的至少16個(gè)頂點(diǎn),矛盾.

(ii){1,3}和{2,3}都不屬于C(X).

由{1,2,4}和{1,2,5}不是X和Y中任一頂點(diǎn)的色集合,可知

下面分情況討論.

若{1,2,3}屬于C(X),則{4,5}不屬于C(Y),顯然也不包含于C(X).此時(shí)C(X)∪C(Y)1,2,4},{1,2,5},{4,5}},有8+n ≤19?3=16.下面只考慮n=8的情形.由C(Y)中的每個(gè)成員均包含顏色3,故{1,4,5}和{2,4,5}不屬于C(Y),則它們屬于C(X).如果{1,2,3}的頂點(diǎn)顏色為1,那么{1,4,5}不能與之染色成功,矛盾;如果{1,2,3}的頂點(diǎn)顏色為2,那么{2,4,5}不能與之染色成功,矛盾.

若{1,2,3}不屬于C(X),則中的成員均不是X和Y中任一頂點(diǎn)的色集合,此時(shí)C(X)∪C(Y),有8+n ≤19?3=16.下面只考慮n=8的情形.由前面的推理知:中的成員均屬于C(Y),且每個(gè)C(ui)至少同時(shí)包含3,4,5中的某兩種色.由對(duì)稱性,不妨設(shè)每個(gè)C(ui)包含3,4,則C(X)只能是以下6個(gè)集合之一：{1,3,4},{2,3,4},{1,2,3,4},{1,3,4,5},{2,3,4,5},{1,2,3,4,5},矛盾.

情形2.2.2中至少有一個(gè)成員屬于C(Y).

此時(shí){1,2} ∈C(ui),i=1,2,···,8,從而C(X)中的成員只能是以下4個(gè)集合之一：{1,2,3},{1,2,3,4},{1,2,3,5},{1,2,3,4,5},矛盾.

情形3|{φ(ui)|i=1,2,···,8}|=3.

不妨設(shè)φ(ui)∈{1,2,3},i=1,2,···,8,則當(dāng)C(vj)是2-子集時(shí)不包含顏色1,不包含顏色2,也不包含顏色3,是3-子集時(shí)不是{1,2,3},因此可以作為Y中頂點(diǎn)色集合的{1,2,3,4,5}的子集的數(shù)目為.當(dāng)17≤n ≤34時(shí),矛盾.下面考慮8≤n ≤16的情況.令,其中

為{1,2,3,4,5}的4-子集,5-子集以及不在1,2,3}}中的3-子集構(gòu)成的集合.

情形3.1{4,5}屬于C(Y).

此時(shí)C(X)中的每個(gè)成員同時(shí)包含顏色4或顏色5,由4和5的對(duì)稱性,不妨設(shè)為4.下面分情況討論.

情形3.1.1{1,4},{2,4},{3,4}中至少有一個(gè)包含于C(X).

此時(shí)C(Y)中的每個(gè)成員均包含顏色4,從而{1,2,5},{1, 3, 5},{2,3,5}和{1,2,3,5}都不屬于C(Y),顯然也不屬于C(X),故C(X)∪C(Y)?C ∪{{1,4},{2, 4},{3,4}}{{1,2,5},{1,3,5},{2,3,5},{1,2,3,5}},即8+n ≤16+3?4=15,15個(gè)集合不能區(qū)分X和Y中的至少16個(gè)頂點(diǎn),矛盾.

情形3.1.2{1,4},{2,4}和{3,4}都不屬于C(X).

此時(shí)C(X)∪C(Y),而恰好包含16個(gè)集合,下面僅考慮n=8的情況.由于C(X)中每個(gè)成員同時(shí)包含顏色4,故{1,2,5},{1,3,5}和{2,3,5}都不屬于C(X),從而只能屬于C(Y),則C(X)中的每個(gè)成員同時(shí)包含顏色1,顏色2和顏色3,因此C(X)中的成員只能是以下2個(gè)集合：{1,2,3,4},{1,2,3,4,5},矛盾.

情形3.2{4,5}不屬于C(Y),顯然也不屬于C(X),則C(Y).

事實(shí)5以下陳述中至多有一句是正確的.

(i){1,2},{1,3}和{2,3}中至少有一個(gè)屬于C(X);

(ii){1,4},{2,4}和{3,4}中至少有一個(gè)屬于C(X);

(iii){1,5},{2,5}和{3,5}中至少有一個(gè)屬于C(X).

事實(shí)5的證明假如(i)-(iii)中至少有兩條是正確的,鑒于(ii)和(iii)的地位是等價(jià)的,故只考慮以下兩種情況.若(i)和(ii)正確,此時(shí)C(Y)中的每個(gè)成員至少同時(shí)包含1,4(或2,4,或3,4),由事實(shí)4(iv)知,只有7個(gè)集合可以作為C(X)中的成員,矛盾;若(ii)和(iii)正確,此時(shí)C(Y)中的每個(gè)成員同時(shí)包含4和5,由事實(shí)4(v)知,只有7個(gè)集合可以作為C(X)中的成員,矛盾.事實(shí)5證畢.

事實(shí)6出現(xiàn)在事實(shí)5中的三條陳述都不正確.

事實(shí)6的證明當(dāng)(i)成立時(shí),C(Y)中的每個(gè)成員至少同時(shí)包含1,2,3中的某一種色,由于1,2,3的對(duì)稱性,不妨設(shè)為1,則可以作為C(Y)中的成員的只能從中選取,其中={{1,2,4},{1,2,5},{1,3,4},{1,3,5},{1,4,5},{1,2,3,4},{1,2,3,5},{1,2,4,5},{1,3,4,5},{1,2,3,4,5}},且||=10.因此中至多有兩個(gè)成員不屬于C(Y),即{1,2,4},{1,2,5},{1,3,4}和{1,3,5}中至少有2個(gè)成員屬于C(Y).此時(shí)以下斷言是成立的:

斷言3{1,2,4},{1,2,5},{1,3,4}和{1,3,5}中恰有2個(gè)屬于C(Y).

斷言3的證明如果{1,2,4},{1,2,5},{1,3,4}和{1,3,5}中至少有3個(gè)屬于C(Y),則{2,4,5},{3,4,5},{2,3,4},{2,3,5},{2,3,4,5}均不屬于C(X),顯然也不屬于C(Y),此時(shí)C(X)∪C(Y)1,2},{1,3},{2,3},{1,2,3}}{{2,4,5},{3,4,5},{2,3,4},{2,3,5},{2,3,4,5}},即8+n ≤15+4?5=14,14個(gè)集合不能區(qū)分X和Y中的至少16個(gè)頂點(diǎn),矛盾.斷言3證畢.

根據(jù)斷言3,繼續(xù)分以下情況進(jìn)行討論.

若{1,2,4}和{1,2,5}屬于C(Y),{1,3,4}和{1,3,5}不屬于C(Y),即

由于{2,4,5},{3,4,5}不能與{1,2,4},{1,2,5}染色成功,故{2,4,5}和{3,4,5}均不屬于C(X).又因?yàn)閧1,4,5}屬于C(Y),則{2,3}不屬于C(X),此時(shí)

如果{1,4,5}的頂點(diǎn)顏色為4,則{2,3,4}與之染色不成功,矛盾;如果{1,4,5}的頂點(diǎn)顏色為5,則{2,3,5}與之染色不成功,矛盾.

若{1,2,4}和{1,3,4}屬于C(Y),{1,2,5}和{1,3,5}不屬于C(Y),即

由于{2,4,5},{3,4,5},{2,3,4,5}不能與{1, 2,4},{1,3,4}染色成功,故

均不屬于C(X).又由{1,4,5}屬于C(Y),由4,5的對(duì)稱性,不妨設(shè)頂點(diǎn)顏色為5,則{2,3}和{2,3,5}都不屬于C(X),此時(shí)C(X)?{{1,2},{1,3},{1,2,3},{2,3,4},{1,2,5},{1,3,5}},6個(gè)集合不能區(qū)分X中的8個(gè)頂點(diǎn),矛盾.

綜上(i)不成立.

當(dāng)(ii)成立時(shí),此時(shí){1,2,4},{1,3,4},{2,3,4}和{1,2,3,4}都不是Y中任一點(diǎn)的色集合,因此

7個(gè)集合不能區(qū)分Y中的至少8個(gè)頂點(diǎn),矛盾.因此(ii)不成立.

至于(iii)可類似(ii)推出矛盾.

至此事實(shí)6證畢.

以上事實(shí)說(shuō)明:含1的2-子集,含2的2-子集,含3的2-子集均不屬于C(X),從而

恰好包含16個(gè)成員.因此{(lán)1,2,3}必為X中某個(gè)頂點(diǎn)的色集合,由1,2,3的對(duì)稱性,不妨設(shè)頂點(diǎn)顏色為1,則{1,4,5}不能與之染色成功.因此{(lán)1,4,5}不屬于C(Y),從而屬于C(X).以下分情況討論.

如果中的成員均不屬于C(Y),則必然屬于C(X),此時(shí)C(X)?{{1,2,3},{1,4,5},{1,2,4},{1,2,5},{1,3,4},{1,3,5},{2,3, 4},{2,3,5}},從而

C(Y)?{{2,4,5},{3,4,5},{1,2,3,4},{1,2,3,5},{1,2,4,5},{1, 3,4,5},{2,3,4,5},{1,2,3,4,5}}.但{2,4,5}與{1,3,5}染色不成功,矛盾.

如果中的成員至少有一個(gè)屬于C(Y),不妨設(shè)為{1,2,4},則{1,4,5}不能與之染色成功,即{1,4,5}不屬于C(X),顯然{1,4,5}不是X和Y中任一頂點(diǎn)的色集合.此時(shí)

即8+n ≤15+1?1=15,15個(gè)集合不能區(qū)分X和Y的至少16個(gè)頂點(diǎn),矛盾.

情形4.

不妨設(shè)φ(ui)∈{1,2,3,4},i=1,2,···,8,則每個(gè)C(vj)均不是2-子集,是3-子集時(shí)不是{1,2,3},{1,2,4},{1,3,4},{2,3,4},是4-子集時(shí)不是{1,2,3,4},因此可以作為Y中頂點(diǎn)色集合的{1,2,3,4,5}的子集的數(shù)目為

當(dāng)12≤n ≤34時(shí),11個(gè)集合不能區(qū)分Y中的n個(gè)頂點(diǎn),矛盾.以下僅考慮8≤n ≤11 的情況.令=,其中

經(jīng)計(jì)算得中包含i的成員有7個(gè),i=1,2,3,4;D中包含5的成員有11個(gè).因此{(lán)1,2},{1,3},{1,4},{2,3},{2,4},{3,4}均不屬于C(X).

情形4.1{1,5},{2,5},{3,5},{4,5}均不屬于C(X).

此時(shí)C(X)∪C(Y),其中

且||=16.顯然中的成員均是C(X)中的成員,故中恰有3個(gè)是C(X)中的成員.由1,2,3,4的對(duì)稱性,可設(shè){1,2,5},{1,3,5},{1,4,5}屬于C(X),則{2,3,5},{2,4,5},{3,4,5}必然屬于C(Y),與VDET染色矛盾.

情形4.2{1,5},{2,5},{3,5},{4,5}中至少有一個(gè)屬于C(X).

此時(shí)中的元素均不屬于C(Y),且有C(Y),而||=5,5個(gè)集合不能區(qū)分Y中的至少8個(gè)頂點(diǎn),矛盾.

因此,K8,n(8≤n ≤34)不存在5-VDET染色,即當(dāng)8≤n ≤34時(shí),.下面給出K8,n的一個(gè)6-VDET染色.

首先在表1中給出了φ34(表1的第一行表示頂點(diǎn)ui(1≤i ≤8)的色集合,第二行表示頂點(diǎn)ui(1≤i ≤8)的顏色,第三行的34(4)表示頂點(diǎn)v1著色4,v1的關(guān)聯(lián)邊u1v1,···,u8v1分別著色3,3,3,3,3,3,3,3,3,3,以下如此類推).當(dāng)8≤j ≤34時(shí),K8,34的6-VDET染色φ34在由所導(dǎo)出的子圖上的限制顯然是K8,j的6-VDET染色φj.

表1 K8,34 的6-VDET 染色φ34

當(dāng)n ≥35時(shí),將對(duì)K8,n的VDET色數(shù)繼續(xù)進(jìn)行研究.