單圈圖的Steiner(n-1)-Wiener指標

來金花，劉蒙蒙

(蘭州交通大學 數(shù)理學院，蘭州 730070)

拓撲指標是從化合物的結構圖中衍生出來的一種數(shù)學不變量，常常被用來描述有機化合物的藥理特征、物理特征以及化學特征.其中Wiener指標和Steinerk-Wiener指標是兩個非常重要的拓撲指標.Wiener指標是由化學家Wiener[1]提出來的，作為一個重要的拓撲指標應用于化學研究中，它是研究有機化合物構造性關系的有用工具.大約在1976年，Wiener指標開始應用于數(shù)學文獻中[2].自此以后，Wiener指標就得到了廣泛的關注和研究，參見文獻[3-10].作為對經典距離定義的推廣，Chartrand等[11]提出了Steiner距離這一概念，2016年Li等[12]用Steiner距離的定義將Wiener指標拓展為Steinerk-Wiener指標.自此國內外專家對Steinerk-Wiener指標問題作了大量的研究.

2016年，Mao等[13]得到了圖乘積的Steinerk-Wiener指標的計算式.Li等[12]在2016年確定了一些特殊圖類的Steinerk-Wiener指標的計算式及樹的Steinerk-Wiener指標的上下界，并給出了樹的Steiner (n-1)-Wiener指標的計算式.對于給定直徑的樹，2018年Lu等[14]給出了Steinerk-Wiener指標的一個緊的下界，并刻畫了達到此下界的極圖.基于此，本文研究單圈圖的Steiner (n-1)-Wiener指標，通過對S中不包含的點分情況討論給出了單圈圖Steiner (n-1)-Wiener指標的計算式，并對單圈圖做變換確定單圈圖Steiner (n-1)-Wiener指標的上界和下界，進而刻畫達到上界和下界的極值圖.

1 基本概念

本文中所有圖都是簡單連通圖，定義G是點集為V(G)，邊集為E(G)的簡單連通圖，其中|G|=|V(G)|.對于?u,v∈V(G),dG(u,v)表示u，v兩點之間的距離，即連接u，v最短路的長度.此外用Cn，Pn，Sn分別表示n階的圈、路和星圖.

定義1G的Wiener指標定義表示圖G中任意兩點的距離之和，即：

(1)

定義2對于S?V(G)，點集S的Steiner距離dG(S)表示G中包含點集S的最小連通子樹的邊數(shù)，即：

dG(S)=min{|E(T)|∶T是G的子樹,S?V(T)}.

(2)

特別地，當S={u,v}時，dG(S)=dG(u,v).因此Steiner距離就是經典距離的一個自然推廣.

定義3對于正整數(shù)k,2≤k≤n-1,G的Steinerk-Wiener指標SWk(G)表示V(G)中所有k子集S的Steiner距離之和，即：

(3)

當k=2時，Steiner 2-Wiener指標就是Wiener指標.

定義4設G為一個n階單圈圖，其中，圈Cg=v1v2…vgv1,G-E(Cg)的連通分支T1，T2，…，Tg都是樹，則單圈圖表示為G=Cg(T1,T2,…,Tg)；當非平凡連通分支數(shù)為1時記G=Cg(T).

2 單圈圖Steiner(n-1)-Wiener指標的計算式

定理2.1設G=Cg(T1,T2,…,Tg)是一個n階單圈圖，|Ti|≥1，i=1,2,…,g.則有

SWn-1(G)=n(n-1)-m-p,

(4)

其中：p為G中懸掛點的個數(shù)；m為|Ti|=1的個數(shù).

證明因為|S|=n-1，即去掉G中任意一個點，剩余所有的點都包含在S中.下面分3種情況討論.

情形1:S中不包含的點是懸掛點.

顯然，要把點集S中的點連接為一個邊數(shù)最小的連通樹需要n-2條邊，即dG(S)=n-2.此時G中有p個懸掛點，則對SWn-1(G)的貢獻為p(n-2).

情形2:S中不包含的點是圈上的點vi且|Ti|=1.

顯然，要把點集S中的點連接為一個邊數(shù)最小的連通樹需要n-2條邊，即dG(S)=n-2.此時G中|Ti|=1的點有m個，則對SWn-1(G)的貢獻為m(n-2).

情形3:其他情況.

要把點集S連接為一個邊數(shù)最小的連通樹，則需要包含G中所有的點，即dG(S)=n-1.這樣的點共有n-p-m個，則對SWn-1(G)的貢獻為(n-p-m)(n-1).綜上所述，可得

SWn-1(G)=p(n-2)+m(n-2)+(n-p-m)(n-1)=n(n-1)+(m+p)(n-2)-(m+p)(n-1)=n(n-1)-m-p.

注意在單圈圖階數(shù)給定的情況下，SWn-1(G)的大小只與m和p的大小有關.

引理2.1令G=Cg(T1,T2,…,Tg)是n階單圈圖|Ti|=li，i=1,2,…,g.則

SWn-1(Cg(Sl1,Sl2,…,Slg))≤SWn-1(G)≤SWn-1

(Cg(Pl1,Pl2,…,Plg)),

(5)

當且僅當G?Cg(Sl1,Sl2,…,Slg)(G?Cg(Pl1,Pl2,…,Plg))時，左(右)邊等號成立.

證明為了方便，令G1=Cg(Sl1,Sl2,…,Slg)，G2=Cg(Pl1,Pl2,…,Plg).由定理2.1知，SWn-1(G)的大小只與p的大小有關.令G1、G2、G中懸掛點的個數(shù)分別為p1、p2、p.顯然，p1≥p≥p2.則有

SWn-1(G1)≤SWn-1(G)≤SWn-1(G2).

當且僅當G?G1(G?G2)時，左(右)邊等號成立.

3 單圈圖Steiner (n-1)-Wiener指標的下界及其極圖

這部分給出n階單圈圖的最小Steiner (n-1)-Wiener指標，并刻畫了達到下界時的極圖.

引理3.1令G=Cg(Sl1,Sl2,…,Slg)是n階單圈圖，則有

SWn-1(G)≥SWn-1(Cg(Sn-g+1)),

(6)

當且僅當G?Cg(Sn-g+1)(如圖1所示)時等號成立.

證明當g=n時，有G?Cg(Sn-g+1)，結論顯然成立.

當g

SWn-1(G)≥SWn-1(Cg(Sn-g+1)),

當且僅當G?Cg(Sn-g+1)時等號成立.

圖1 圖Cg(Sn-g+1)Fig.1 The graph of Cg(Sn-g+1)

當單圈圖圈長固定時，由引理2.1，3.1直接可得單圈圖的下界.即

定理3.1令G=Cg(T1,T2,…,Tg)是一個n階單圈圖.則有

SWn-1(G)≥SWn-1(Cg(Sn-g+1)),

(7)

當且僅當G?Cg(Sn-g+1)時等號成立.

引理3.2令Cg(Sn-g+1)是n階單圈圖，g≠n.則有

SWn-1(Cg(Sn-g+1))=SWn-1(Cg-1(Sn-g+2)).

(8)

證明因為g≠n，在Cg(Sn-g+1)，Cg-1(Sn-g+2)中m+p=n-1為定值.則由定理2.1知,

SWn-1(Cg(Sn-g+1))=SWn-1(Cg-1(Sn-g+2))=n(n-1)-(n-1)=(n-1)2.

定理3.2令G=Cg(T1,T2,…,Tg)是一個n階單圈圖.則有

SWn-1(G)≥n(n-2),

(9)

當且僅當G?Cn時等號成立.

證明當g=n時，m+p=n.則有

SWn-1(G)≥n(n-1)-n=n(n-2),

當且僅當G?Cn時等號成立.

當3≤g

SWn-1(G)≥SWn-1(Cg(Sn-g+1))=(n-1)2,

當且僅當G?Cg(Sn-g+1)時等號成立.

顯然，(n-1)2>n(n-2).

綜上，SWn-1(G)≥n(n-2)，當且僅當G?Cn時等號成立.

4 單圈圖Steiner (n-1)-Wiener指標的上界及其極圖

這一部分中給出n階單圈圖的最大Steiner (n-1)-Wiener指標，并刻畫了達到上界時的極圖.

定理4.1令G=Cg(T1,T2,…,Tg)是n階單圈圖，且|Ti|=li，i=1,2,…,g.當單圈圖圈長固定時，則有

SWn-1(G)≤n(n-1)-g,

(10)

當且僅當G?Cg(Pl1,Pl2,…,Plg)時，等號成立.

證明當單圈圖圈長固定且圖中的懸掛分支為路時，m+p=g為定值.則由定理2.1，引理2.1知

SWn-1(G)≤n(n-1)-g,

當且僅當G?Cg(Pl1,Pl2,…,Plg)時，等號成立.

定理4.2設G=Cg(T1,T2,…,Tg)是一個n階單圈圖.則有

SWn-1(G)≤n(n-1)-3,

(11)

當且僅當G?C3(Pl1,Pl2,Pl3)(如圖2所示)時等號成立.

證明由引理2.1，定理4.1知:

SWn-1(G)≤n(n-1)-g≤n(n-1)-3,

當且僅當G?C3(Pl1,Pl2,Pl3)時等號成立.

圖2 具有最大Steiner (n-1)-Wiener指標的單圈圖Fig.2 The maximum unicyclic graph of Steiner (n-1)- Wiener index

5 結論

在現(xiàn)有國內外專家對此問題研究的基礎上，首先給出了單圈圖Steiner (n-1)-Wiener指標的計算式；其次，確定了單圈圖Steiner (n-1)-Wiener指標的上、下界，并刻畫了達到上、下界時的極圖，對下一步研究簡單連通圖的Steinerk-Wiener指標具有很好的借鑒意義.