單圈圖的Steiner k-general Wiener指數

王 笑,耿顯亞

(安徽理工大學 數學與大數據學院,安徽 淮南232001)

本文中所研究的圖都是簡單、有限和無向的.本文所用的符號和術語請參考文獻[1].設G是一個至少2階的連通圖,S是G的非空頂點集,則Steiner距離d(S)表示G中包含點集S的最小連通子樹的邊數.如果G的子圖T是樹并且S?V(T),則稱T是S的Steiner樹或S-Steiner樹.Steiner樹在計算機網絡中有廣泛的應用,有關Steiner距離的更多詳細信息,請參考文獻[2-6].

拓撲指數是一種由化合物結構導出的數學不變量,常用于描述有機化合物的物理、化學和藥理特性,其中Wiener和Steinerk-Wiener指數是兩個重要的拓撲指數,在對化學的研究中,它們是研究有機化合物結構關系的有用工具.2016年Li等[7]將Wiener指數推廣到Steinerk-Wiener指數,并確定了一些特殊圖類的Steinerk-Wiener指數的計算式及樹的Steinerk-Wiener指數的上下界,有關Steinerk-Wiener指數的更多研究,請參考文獻[8-15].本文進一步推廣了Steinerk-Wiener指數,給出Steinerk-general Wiener定義以及單圈圖的下界,并得到對應的極圖.

1 基本概念

定義1[3]對于S?V(G),點集S的Steiner距離d(S)表示G中包含點集S的最小連通子樹的邊數,即

d(S)=min{|E(T)|:T是G的子樹S?V(T)}

定義2[8]Steinerk-Wiener指數定義為

當k=2時,Steiner 2-Wiener指數就是wiener指數.

定義3 Steinerk-general Wiener指數定義為

特別地,當m=1時,Steinerk-general Wiener指數就是Steinerk-Wiener指數.

圖1 圖C3(Sn-2)

2 主要結論

設G,H是兩個非平凡的連通圖,且u∈V(G),v∈V(H),設GuH是通過用v重合u從G和H中獲得的圖.

引理2.1 設G是一個非平凡的連通圖,且u∈V(G),Tm是一個非平凡的樹(m階),且v∈V(Tm),通過刪除Tm的邊從GuTm獲得GuSm并將Tm/{u(v)}的頂點連接到u(v)上,k是一個整數,當2≤k≤n-2時,則有

當且僅當GuTm?GuSm時等號成立.

證明對于任意的S?V(GuTm)=V(GuSm),|S|=k,下面分3種情況討論.

通過反復應用引理2.1的計算,得到以下推論.

推論 2.1 令G=Ct(Tt1,Tt2,…,Ttc)≠Cn,k是一個整數,且2≤k≤n-1,則有

當且僅當G?Ct(St1,St2,…,Stc)等號成立.

引理2.2 設Ct(St1,St2,…,Stc)≠Cn,k是一個整數,且2≤k≤n-1,則有

當且僅當(Ct(St1,St2,…,Stc))?C3(Sn-2)等號成立.

證明令G=Ct(St1,St2,…,Stc),將G和C3(Sn-2)的頂點集表示為V(G)=V(C3(Sn-2))={u0,u2,…,un-1},其中u0是G割點,是C3(Sn-2)唯一一個n-1度頂點.對于任意S?V(G),|S|=k,Steiner樹TG(S)是毛毛蟲樹.

引理2.3 設k是一個正整數,且3≤k≤n-2,則

定理2.4 對于G∈UC(n)(n≥6),k是一個整數,且3≤k≤n-2,則有

當且僅當G?C3(Sn-2)時等號成立.

3 結 語

在現有國內外專家研究的基礎上,本文進一步推廣了Steinerk-Wiener指數,給出了單圈圖的Steinerk-general Wiener指數的下界,并確定了下界時的極圖,為接下來關于Steinerk-Wiener的更多研究提供了思路.