圖的相對結合數與圖的結構的兩個新結果

鄧毅雄,曾愛祥

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

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

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

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

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

1 主要結果

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

定理6 對任意n階（n≥4）連通圖G，則rb(G)=4-n當且僅當G具有如下結構之一：

2 定理證明

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

圖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}對應的K1與G[V(S∪N(S))]的2K2的鄰接關系只能為如圖2（a）（b）（c）所示情況之一。

圖2 K1與2K2的鄰接關系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］鄧毅雄.圖的相對結合數［J］.華東交通大學學報，1995,12（1）：92-96.

［4］鄧毅雄.圖的相對結合數的進一步結果［J］.華東交通大學學報，1997,14（1）：64-69.