鄭學謙

(山西工程科技職業(yè)大學，山西 晉中 030619)

0 引言

點集S的Steiner距離d(S)間題是組合優(yōu)化中經典的問題,在現代生產、生活中有著十分廣泛的應用.1947年H.Wiener提出連通圖G的Wiener指數[1]，1993年M.Randics 提出了超Wiener指數WW(G)的概念[2]，2016年李學良，毛亞平和Gutman提出了k-Steiner Wiener指數SWk(G)[3]，同時給出了樹、完全圖Kn、完全二部圖Ka,b的SWk(T)指數的計算公式．2016年劉中柱，程曉勝給出了給定點著色數和匹配數的圖類中的k-Steiner Wiener指數的下界并刻畫了極圖[4].2017年劉中柱，何莉給出了給定匹配數的樹中的k-Steiner Wiener指數SWk(G)的極小值，并刻畫了極圖[5]．2018年Niko Tratnik給出了網圖的k-Steiner Wiener指數和超k-Steiner Wiener指數[6].在此基礎上，本文利用組合不等式給出了星勺圖Stn-1P1C4和R(4，1×n)型圖的k-Steiner Wiener指數的計算公式.

1 相關概念

定義1[7]由圈C4的點u1與n條p2路粘接所得到的圖形，稱為R(4，1×n)型圖(圖1)．

圖1 R(4，1×n)型圖

定義2[8]把n個頂點的星圖與圈C4由一條長為1的路連接，其中路的一端點與星圖的中心粘結，另一端點與圈的一個頂點粘結，所構成的圖稱為星勺圖，記為Stn-1P1C4(圖2)．

圖2 星勺圖Stn-1P1C4

定義3[3]點集S的Steiner距離d(S)是指包含子集S的最小子樹的邊數即d(S)=min{|E(T)|:S?V(T),T是G的子樹}．k-Steiner Wiener指數SWk(G)，

2 主要結論

定理1對于R(4，1×n)型圖，

證明 對于R(4，1×n)型圖，U={u1,u2,u3,u4}，W={v1,…,vn-4}

當k=3,4時，S∩U=?,或者S∩W=?,或者S∩U≠?且S∩W≠?．假設S∩U=?,S?W．則d(S)=k.假設S∩W=?,S?U．則當k=3時，d(S)=2;當k=4時，d(S)=3.

假設S∩U≠?且S∩W≠?．不失一般性S={u1,u2,…,ut,v1,…,vk-t},t=1,…,4,當k=3時，d(S)=2，3,4;當k=4時，d(S)=3,4,5.

當k>4時，S∩U=?且S∩W≠?或者S∩U≠?且S∩W≠?：假設S∩U=?且S∩W≠?,S?W．則，d(S)=k.假設S∩U≠?且S∩W≠?．

不失一般性S={u1,u2,…,ut,v1,…,vk-t},t=1,…,4,容易得到d(S)分別k-1,k,k+1.

證明

定理2對于星勺圖Stn-1P1C4，

SWk(Stn-1P1C4)=

證明 對于星勺圖Stn-1P1C4，U={u0,u1,u2,u3,u4}，W={v1,…,vn-5}對于任意S?V(G),|S|=k．

當k<5時，S∩U=?,或者S∩W=?,或者S∩U≠?且S∩W≠?．假設S∩U=?,S?W．則d(S)=k.假設S∩W=?,S?U．則當k=3時，d(S)=3，2;當k=4時，d(S)=4，3;當k=5時，d(S)=4.

假設S∩U≠?且S∩W≠?．不失一般性S={u1,u2,…,ut,v1,…,vk-t},t=0,1,…,4,當k=3時，d(S)=2，3,4,5;當k=4時，d(S)=3,4,5;當k=5時，d(S)=4,5,6,7.

SW4(Stn-1P1C4)=

當k>5時，S∩U=?且S∩W≠?或者S∩U≠?且S∩W≠?：假設S∩U=?且S∩W≠?,S?W．則，d(S)=k.假設S∩U≠?且S∩W≠?．

不失一般性，S={u1,u2,…,ut,v1,…,vk-t},t=0,1,…,4,容易得到d(S)分別k-1,k,k+1,k+2,則

SWk(Stn-1P1C4)=