圖的最小度和無矛盾連通數

嚴政，趙小鵬，慈永鑫

長江大學信息與數學學院，湖北 荊州 434023

1 基本結果

關于圖G的無矛盾染色，CZAP等[2]首先確定了路徑的無矛盾連通數。

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

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

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

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

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

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

設t是正整數，G的t-冠(corona)是指向G的每個頂點添加t條懸掛邊所構成的圖。

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

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

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

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

關于無矛盾連通數的更多結論,詳見文獻[3]和[10,11]。

2 主要結果

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

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

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

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

由于δ(G)≥s+2，所以H0中的每一個頂點都至少連接一條割邊。設y為G中與H0關聯的割邊數，則：

整理得：

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。設G中與H0相關聯的割邊分別為e1,e2,…,ey，則G={e1,e2,…,ey}有y+1個連通分支，記為H0,H1,…,Hy。因為δ(G)≥s+2≥4，所以對于任意的Hi(1≤i≤y)，都存在v∈V(Hi)，使得N(v)?V(Hi)，從而每個Hi至少有δ(G)+1個頂點。于是：

≥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可知，當k≥2時，cfc(G)≤k。

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

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

δ(G)=s+1

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

特別地，當s=k時，得到下述推論。

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

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

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

情形1G沒有割邊，即G由非平凡塊構成。

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

情形2G僅有1條割邊。

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

情形3G有2條割邊。

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

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

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

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

情形4G有3條割邊且不相交于同一點。

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

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

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

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

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

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

情形5G有3條割邊且相交于一點。

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

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

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

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

引理3設G是一個由任意2-連通圖中每個頂點都懸掛t條邊所構成的圖，則：

t≤cfc(G)≤t+1

證明對于有割邊的連通圖G，由于每個頂點懸掛t條邊，因此h(G)=t。根據命題2，有：

t≤cfc(G)≤t+1

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

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

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

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

情形1t=2。

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

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

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

情形2t≥3。

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

2.3 階為n最小度為δ的連通圖G的無矛盾連通數

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

則：

cfc(G)≤k

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

則：

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

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

其中：

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

則：

cfc(G)≤k

其中：

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

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

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

則：

cfc(G)≤k

3 結語

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