圖的相對(duì)結(jié)合數(shù)與圖的結(jié)構(gòu)的兩個(gè)新結(jié)果

鄧毅雄,曾愛(ài)祥

（1.華東交通大學(xué)軟件學(xué)院，江西南昌 330013；2.江西省新干縣湖中學(xué)，江西吉安 331303）

文中用到的幾個(gè)記號(hào)的說(shuō)明：設(shè)有圖G1，G2，G3，我們用G1+G2表示G1中各點(diǎn)與G2中各點(diǎn)分別鄰接所得之圖，即V(G1+G2)=V(G1)∪V(G2)，E(G1+G2)=E(G1)∪E(G2)∪{e|e=uv，u∈V(G1)，v∈V(G2)}；用G1+G2+G3表示G1中各點(diǎn)與G2中各點(diǎn)分別鄰接，而G2中各點(diǎn)與G3中各點(diǎn)亦分別鄰接所得之圖，其它情形類似定義。設(shè)S是G的一個(gè)點(diǎn)集，用G[S]表示S在G中的生成子圖，即V(G[S])=S，E(G[S])={e|e=uv，u，v∈S，且e∈E(G)}。以下我們用Fm表示所有可能的m階圖中的某一個(gè)圖。用δ(G)表示圖G的最小度，?為空集符號(hào)。

在對(duì)圖的相對(duì)結(jié)合數(shù)的討論中，考慮滿足rb(G)=k的圖類是一個(gè)非常有趣的問(wèn)題，在文獻(xiàn)［3-5］中，對(duì)這方面問(wèn)題進(jìn)行了一定討論，本文對(duì)這個(gè)問(wèn)題的進(jìn)一步討論，得到了兩個(gè)相關(guān)的結(jié)果。下面我們首先將文獻(xiàn)［3-4］中的有關(guān)結(jié)果歸納如下：

定理1［4］對(duì)任意2-n≤k≤n-2，k≠3-n或n-3，存在n階連通圖G，使rb(G)=k。

定理2［3］設(shè)G是n階連通圖（n≥2），則rb(G)=2-n當(dāng)且僅當(dāng)G=Kn；rb(G)=n-2當(dāng)且僅當(dāng)G=K1，n-1。

1 主要結(jié)果

定理5 對(duì)任意n階（n≥6）連通圖G，rb(G)=n-6當(dāng)且僅當(dāng)G為下列圖之一：

定理6 對(duì)任意n階（n≥4）連通圖G，則rb(G)=4-n當(dāng)且僅當(dāng)G具有如下結(jié)構(gòu)之一：

2 定理證明

定理5的證明 首先我們注意到，若G取得定理所給出的圖，易于驗(yàn)證它們均滿足rb(G)=n-6，也即充分性成立，定理的證明關(guān)鍵是其必要性。

圖1 滿足情形1.2的所有可能的4階圖Fig.1 The graphsof order 4 that content case 1.2

情形1.2.1 若G[V(S∪N(S))]=2K2，即為圖1（a），則由G的連通性，N(S)={u}對(duì)應(yīng)的K1與G[V(S∪N(S))]的2K2的鄰接關(guān)系只能為如圖2（a）（b）（c）所示情況之一。

圖2 K1與2K2的鄰接關(guān)系Fig.2 Ad jacent relationship of K1 and 2K2

圖3 一類不滿足rb(G)=n-6的圖Fig.3 A classgraph of discontent rb(G)=n-6

［1］CHARTRAND G，LESNIAK L.Graphsand digraphs［M］.3 rd ed.London：Chapman&Hall，1996：1-106.

［2］ JA BONDY，USR MURTY.Graph theory w ith application［M］.New York：Elsevier Science Publishing Company，1976：1-65.

［3］鄧毅雄.圖的相對(duì)結(jié)合數(shù)［J］.華東交通大學(xué)學(xué)報(bào)，1995,12（1）：92-96.

［4］鄧毅雄.圖的相對(duì)結(jié)合數(shù)的進(jìn)一步結(jié)果［J］.華東交通大學(xué)學(xué)報(bào)，1997,14（1）：64-69.