圖的最小度和無(wú)矛盾連通數(shù)

嚴(yán)政，趙小鵬，慈永鑫

長(zhǎng)江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023

1 基本結(jié)果

關(guān)于圖G的無(wú)矛盾染色，CZAP等[2]首先確定了路徑的無(wú)矛盾連通數(shù)。

命題1[2]設(shè)Pn表示有n條邊的路徑，則：

設(shè)C(G)是G中由割邊誘導(dǎo)的子圖，用Q1,Q2,…,Ql表示C(G)的分支，記h(G)=max{cfc(Qi):Qi是C(G)中的分支}。

命題2[2]設(shè)G是一個(gè)有割邊的連通圖，則：

h(G)≤cfc(G)≤h(G)+1

對(duì)于階為n的連通圖G，1≤cfc(G)≤n-1；當(dāng)且僅當(dāng)G=Kn時(shí)，cfc(G)=1；當(dāng)且僅當(dāng)G=K1,n-1時(shí)，cfc(G)=n-1[3，5，10]。若G是非完全圖，則cfc(G)≥2。特別地，對(duì)于2-連通圖，cfc(G)=2；文獻(xiàn)[3，11]進(jìn)一步得到，對(duì)于非完全2-邊連通圖，cfc(G)=2。

命題3[2]設(shè)G是一個(gè)非完全2-連通圖，則cfc(G)=2。

設(shè)t是正整數(shù)，G的t-冠(corona)是指向G的每個(gè)頂點(diǎn)添加t條懸掛邊所構(gòu)成的圖。

命題4[2]設(shè)Cn=v1v2,…,vn(n≥4)是一個(gè)圈，G是它的2-冠，則cfc(G)=3。

命題5[2]設(shè)G是一個(gè)有割邊的連通圖，則cfc(G)≤max{2，|E(C(G))|}。

引理1[2]設(shè)G是一個(gè)連通圖，則從G的每一個(gè)非平凡塊中適當(dāng)選擇一條邊，可形成G的一個(gè)匹配。

引理2[2]設(shè)G是一個(gè)2-連通圖，e∈E(G)，則G中任意2個(gè)不同的頂點(diǎn)u和v之間存在1條包含e的u-v路徑。

關(guān)于無(wú)矛盾連通數(shù)的更多結(jié)論,詳見(jiàn)文獻(xiàn)[3]和[10,11]。

2 主要結(jié)果

2.1 階小于ks+2s+3k+6(s≥k≥2)的連通圖的無(wú)矛盾連通數(shù)

定理1設(shè)G是一個(gè)階為n(n≥2)的連通圖，其中n≤ks+2s+3k+5(s≥k≥2)。如果δ(G)≥s+2，則cfc(G)≤k。

證明先用反證法證明G至多有k條割邊。假設(shè)G有l(wèi)(l≥k+1)條割邊，則刪除G的所有割邊得到l+1個(gè)連通分支，設(shè)H0是其中最小的分支。

情形1|V(H0)|=a≤s+2。

由于δ(G)≥s+2，所以H0中的每一個(gè)頂點(diǎn)都至少連接一條割邊。設(shè)y為G中與H0關(guān)聯(lián)的割邊數(shù)，則：

整理得：

a(s+2)≤a(a-1)+y

即：

y≥a(s-a+3)

又：

a(s-a+3)-(s+2)=a(s+2+1-a)-(s+2)

=(s+2)(a-1)+a(1-a)

=(a-1)(s+2-a)≥0

因此，y≥s+2≥k+2。設(shè)G中與H0相關(guān)聯(lián)的割邊分別為e1,e2,…,ey，則G={e1,e2,…,ey}有y+1個(gè)連通分支，記為H0,H1,…,Hy。因?yàn)棣?G)≥s+2≥4，所以對(duì)于任意的Hi(1≤i≤y)，都存在v∈V(Hi)，使得N(v)?V(Hi)，從而每個(gè)Hi至少有δ(G)+1個(gè)頂點(diǎn)。于是：

≥y(s+3)

≥(k+2)(s+3)

=ks+2s+3k+6

與n≤ks+2s+3k+5矛盾。

情形2|V(H0)|≥s+3。

由δ(G)≥s+2，得：

≥(l+1)(s+3)

≥(k+2)(s+3)

=ks+2s+3k+6

這與n≤ks+2s+3k+5矛盾。

因此G至多有k條割邊。由命題5可知，當(dāng)k≥2時(shí)，cfc(G)≤k。

定理1中的界是緊的。構(gòu)造圖Gk+1如下：記H0,H1,…,Hk+1均是階為s+2的完全圖，取H0中任意一點(diǎn)分別與H1,H2,…,Hk+1中的一點(diǎn)連接。此時(shí)，有：

|V(Gk+1)|=(k+2)(s+2)=ks+2s+2k+4

δ(G)=s+1

顯然，cfc(Gk+1)=k+1。

特別地，當(dāng)s=k時(shí)，得到下述推論。

推論1設(shè)G是一個(gè)階為n(n≥2)的連通圖，如果n≤k2+5k+5(k≥2)且δ(G)≥k+2，則cfc(G)≤k。

推論2設(shè)G是一個(gè)階為n(n≥2)的非完全連通圖，如果n≤5s+14(s≥2)且δ(G)≥s+2，則當(dāng)G存在3條割邊且相交于一點(diǎn)時(shí)，cfc(G)=3；否則cfc(G)=2。

證明由定理1可知，滿足條件的G至多有i條割邊，記為ei(i≤3)。

情形1G沒(méi)有割邊，即G由非平凡塊構(gòu)成。

根據(jù)引理1，從每一個(gè)非平凡塊中選取一條邊構(gòu)成匹配M，此時(shí)令c(M)=1，c(E(G)-M)=2。

情形2G僅有1條割邊。

從G中所有的非平凡塊中選取一條邊構(gòu)成匹配M，令c(e1∪M)=1，c(E(G)-e1∪M)=2。

情形3G有2條割邊。

刪除2條割邊有3個(gè)連通分支，分別記為H0，H1，H2。

1)如果e1和e2相鄰，則令c(e1)=1，c(e2)=2。

2)如果e1和e2不相鄰，則令c(e1)=c(e2)=2。

現(xiàn)在對(duì)每個(gè)連通分支進(jìn)行染色，從每個(gè)Hi(0≤i≤2)中的非平凡塊中取一條邊構(gòu)成匹配M，此時(shí)令c(M)=1，c(E(G)-{e1,e2}∪M)=2。

情形4G有3條割邊且不相交于同一點(diǎn)。

刪除3條割邊有4個(gè)連通分支，分別記為H0，H1，H2，H3。

1)如果ei(1≤i≤3)各不相鄰，即割邊之間沒(méi)有交點(diǎn)，此時(shí)令c(e1)=c(e2)=c(e3)=1。

2)如果ei(1≤i≤3)中恰有2條割邊相鄰，不失一般性，假設(shè)e1與e2相鄰，此時(shí)e3和e1，e2均沒(méi)有交點(diǎn)，則令c(e1)=c(e3)=1，c(e2)=2。

3)如果e1和e2相鄰，e2和e3相鄰并且e1和e3不相鄰，則令c(e1)=c(e3)=1，c(e2)=2。

接下來(lái)從每個(gè)Hi(0≤i≤3)中的非平凡塊中取一條邊構(gòu)成匹配M，令c(M)=2，c(E(G)-{e1,e2,e3}∪M)=1。

根據(jù)引理2可以驗(yàn)證，上述情形1～4中任意2個(gè)頂點(diǎn)之間都存在一條只需要2種顏色的無(wú)矛盾連通路徑，即cfc(G)≤2，顯然cfc(G)≥2，從而cfc(G)=2。

情形5G有3條割邊且相交于一點(diǎn)。

由于任意2條割邊之間都僅存在1條路徑，因此3條割邊的顏色互不相同。即cfc(G)≥3。另一方面，由定理1可知，cfc(G)≤3。于是cfc(G)=3。

綜合上述所有情形，推論2成立。

推論3設(shè)G是一個(gè)階為n(n≥2)的非完全連通圖，如果n≤4s+11(s≥2)且δ(G)≥s+2，則cfc(G)=2。

證明由定理1可知，滿足條件的G至多存在2條割邊，一方面，由推論2中情形1～情形3知，存在1種只需要2種顏色的無(wú)矛盾連通染色，于是cfc(G)≤2。另一方面，對(duì)于任意的非完全連通圖，有cfc(G)≥2，從而cfc(G)=2。

引理3設(shè)G是一個(gè)由任意2-連通圖中每個(gè)頂點(diǎn)都懸掛t條邊所構(gòu)成的圖，則：

t≤cfc(G)≤t+1

證明對(duì)于有割邊的連通圖G，由于每個(gè)頂點(diǎn)懸掛t條邊，因此h(G)=t。根據(jù)命題2，有：

t≤cfc(G)≤t+1

2.2 Cn(n≥3)的t-冠(t≥2)的無(wú)矛盾連通數(shù)

對(duì)一種特殊的2-連通圖Cn，文獻(xiàn)[2]研究了Cn(n≥4)的2-冠，得到其無(wú)矛盾連通數(shù)為3。下面給出Cn(n≥3)的t-冠(t≥2)的無(wú)矛盾連通數(shù)。

定理2設(shè)Cn=v1,v2,…,vn(n≥3)是一個(gè)圈，G是它的t-冠，其中t≥2,則：

證明由于G是Cn中每個(gè)頂點(diǎn)通過(guò)添加t條懸掛邊得到的圖，即h(G)=t。由引理3，有cfc(G)≥t。下面分2種情形討論。

情形1t=2。

1)如果n≥4，則由命題4可知，cfc(G)=3。

2)如果n=3，此時(shí)假設(shè)cfc(G)=2。如圖1(a)所示，與頂點(diǎn)vi(1≤i≤3)相連的2個(gè)懸掛點(diǎn)分別記為xi，yi。因?yàn)榕cvi相連的懸掛邊之間僅有1條路徑，所以需染不同的顏色，令c(vixi)=1，c(viyi)=2(1≤i≤3)。對(duì)于C3，由命題3可知，2-連通圖的無(wú)矛盾連通數(shù)為2。因此根據(jù)對(duì)稱性，不妨令c(v1v2)=1，c(v1v3)=c(v2v3)=2。由引理2可知，對(duì)C3中任意2個(gè)頂點(diǎn)之間的路徑均選擇通過(guò)染顏色1的邊。這時(shí)任意選擇x1-x2之間的路徑，都無(wú)法找到一條無(wú)矛盾連通路徑。與假設(shè)矛盾。因此cfc(G)≥3。另一方面，由引理3知，cfc(G)≤3，故cfc(G)=3。

圖1 圈的懸掛邊Fig.1 Pendant edges of cycle

情形2t≥3。

由上述易知，只需證明cfc(G)≤t。如圖1(b)所示，定義染色規(guī)則如下：不失一般性，在Cn中選擇任意2條邊并給它們?nèi)绢伾?和2，Cn中所有剩余的邊都染顏色3，與每個(gè)vi相鄰的K1,t分別用1,2,…,t進(jìn)行染色。此時(shí)，上述染色方式使得G中任意,2個(gè)頂點(diǎn)之間都存在一條無(wú)矛盾連通路徑，于是cfc(G)≤t。證畢。

2.3 階為n最小度為δ的連通圖G的無(wú)矛盾連通數(shù)

命題6[5]設(shè)G是一個(gè)階為n(n≥2)的連通圖，k(k≥2)為整數(shù)。如果：

則：

cfc(G)≤k

命題7[6]設(shè)G是一個(gè)階為n(n≥2)且包含割邊的連通圖，k(k≥2)為整數(shù)。如果：

則：

cfc(G)≤k或 Δ(C(G))≤k+1

引理4[12]設(shè)G是一個(gè)具有t條割邊且最小度為δ=δ(G)的n階連通圖，則：

其中：

定理3設(shè)G是一個(gè)階為n(n≥2)的連通圖，k(k≥2)為整數(shù)，如果：

則：

cfc(G)≤k

其中：

證明用反證法。假設(shè)cfc(G)≥k+1，由命題5知，|E(C(G))|≥k+1，根據(jù)引理4，有：

特別地，當(dāng)δ(G)≥k+2時(shí)，m=0。于是有下述推論。

推論4設(shè)G是一個(gè)階為n(n≥2)且δ(G)≥k+2(k≥2)的連通圖，如果：

則：

cfc(G)≤k

3 結(jié)語(yǔ)

在已有無(wú)矛盾染色理論基礎(chǔ)之上，利用圖的最小度研究無(wú)矛盾連通數(shù)不超過(guò)k的圖類，同時(shí)給出一些無(wú)矛盾連通數(shù)為2和3的最小度條件。此外，能否根據(jù)最大度或添加最大度條件去討論圖的無(wú)矛盾染色，在后續(xù)研究中可以嘗試。目前只針對(duì)特殊圖類進(jìn)行了研究，如何確定任意給定連通圖的無(wú)矛盾染色需要進(jìn)一步的研究。