完全二部圖的超k-Steiner Wiener指數(shù)

喬曉云

(山西大學商務(wù)學院，山西 太原 030031)

0 引言

1 預(yù)備知識

定義1[6]二部圖是指一個圖，它的頂點集可以分解為兩個非空子集X和Y,使得每條邊都有一個端點在X中，另一個端點在Y中.完全二部圖是指二部圖中X的每個頂點都與Y的每個頂點相連.若|X|=m,|Y|=n,則這樣的圖記為Km,n.

2 主要結(jié)論

定理：設(shè)G=Km,n(1≤m≤n)為完全二部圖，2≤k≤m+n,則

證明 設(shè)G=Km,n(1≤m≤n)為完全二部圖，V(Km,n)=U∪W,其中U={u1,u2,…,um},W={w1,w2,…,wn}.

(H1)當2≤k≤m時，對于?S?V(G),|S|=k,則有以下三種情況S∩U=φ或者S∩W=φ或者S∩U≠φ,S∩W≠φ.

①對于S∩U=φ,則S?W.不失一般性，令S={w1,w2,…,wk},E′={u1w1,u1w2,…,u1wk},則G[E′]是包含S的Steiner樹，則d(S)≤k.另一方面，由于G=Km,n是完全二部圖，則包含S的任何樹至少有k條邊，即d(S)≥k.所以d(S)=k.

②對于S∩W=φ,同理可得d(S)=k.

③對于S∩U≠φ,S∩W≠φ,不失一般性，令S={u1,u2,…,ut,w1,w2,…,wk-t},E′={u1w1,w1u2,w1u3…,w1ut,u1wt,…,u1wk-t},則G[E′]是包含S的Steiner樹，則d(S)≤k-1.另一方面，|S|=k,則連接S的任何樹至少有k-1條邊，即d(S)≥k-1.所以d(S)=k-1

由定義得

(H2)當m≤k≤n時，對于?S?V(G),|S|=k,則有以下兩種情況S∩U=φ或者或者S∩U≠φ,S∩W≠φ.根據(jù)(H1)的情況①③同理可得S∩U=φ時，d(S)=k.S∩U≠φ,S∩W≠φ時，d(S)=k-1.

由定義得

(H3)當n≤k≤m+n時，對于?S?V(G),|S|=k,則S∩U≠φ,S∩W≠φ.根據(jù)(H1)的情況③同理可得.S∩U≠φ,S∩W≠φ時，d(S)=k-1.

由定義得

綜上所述，定理得證.