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

來(lái)金花，劉蒙蒙

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

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

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

1 基本概念

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

定義1G的Wiener指標(biāo)定義表示圖G中任意兩點(diǎn)的距離之和，即：

(1)

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

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

(2)

特別地，當(dāng)S={u,v}時(shí)，dG(S)=dG(u,v).因此Steiner距離就是經(jīng)典距離的一個(gè)自然推廣.

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

(3)

當(dāng)k=2時(shí)，Steiner 2-Wiener指標(biāo)就是Wiener指標(biāo).

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

2 單圈圖Steiner(n-1)-Wiener指標(biāo)的計(jì)算式

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

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

(4)

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

證明因?yàn)閨S|=n-1，即去掉G中任意一個(gè)點(diǎn)，剩余所有的點(diǎn)都包含在S中.下面分3種情況討論.

情形1:S中不包含的點(diǎn)是懸掛點(diǎn).

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

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

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

情形3:其他情況.

要把點(diǎn)集S連接為一個(gè)邊數(shù)最小的連通樹，則需要包含G中所有的點(diǎn)，即dG(S)=n-1.這樣的點(diǎn)共有n-p-m個(gè)，則對(duì)SWn-1(G)的貢獻(xiàn)為(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的大小有關(guān).

引理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)

當(dāng)且僅當(dāng)G?Cg(Sl1,Sl2,…,Slg)(G?Cg(Pl1,Pl2,…,Plg))時(shí)，左(右)邊等號(hào)成立.

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

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

當(dāng)且僅當(dāng)G?G1(G?G2)時(shí)，左(右)邊等號(hào)成立.

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

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

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

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

(6)

當(dāng)且僅當(dāng)G?Cg(Sn-g+1)(如圖1所示)時(shí)等號(hào)成立.

證明當(dāng)g=n時(shí)，有G?Cg(Sn-g+1)，結(jié)論顯然成立.

當(dāng)g

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

當(dāng)且僅當(dāng)G?Cg(Sn-g+1)時(shí)等號(hào)成立.

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

當(dāng)單圈圖圈長(zhǎng)固定時(shí)，由引理2.1，3.1直接可得單圈圖的下界.即

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

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

(7)

當(dāng)且僅當(dāng)G?Cg(Sn-g+1)時(shí)等號(hào)成立.

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

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

(8)

證明因?yàn)間≠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)是一個(gè)n階單圈圖.則有

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

(9)

當(dāng)且僅當(dāng)G?Cn時(shí)等號(hào)成立.

證明當(dāng)g=n時(shí)，m+p=n.則有

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

當(dāng)且僅當(dāng)G?Cn時(shí)等號(hào)成立.

當(dāng)3≤g

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

當(dāng)且僅當(dāng)G?Cg(Sn-g+1)時(shí)等號(hào)成立.

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

綜上，SWn-1(G)≥n(n-2)，當(dāng)且僅當(dāng)G?Cn時(shí)等號(hào)成立.

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

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

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

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

(10)

當(dāng)且僅當(dāng)G?Cg(Pl1,Pl2,…,Plg)時(shí)，等號(hào)成立.

證明當(dāng)單圈圖圈長(zhǎng)固定且圖中的懸掛分支為路時(shí)，m+p=g為定值.則由定理2.1，引理2.1知

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

當(dāng)且僅當(dāng)G?Cg(Pl1,Pl2,…,Plg)時(shí)，等號(hào)成立.

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

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

(11)

當(dāng)且僅當(dāng)G?C3(Pl1,Pl2,Pl3)(如圖2所示)時(shí)等號(hào)成立.

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

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

當(dāng)且僅當(dāng)G?C3(Pl1,Pl2,Pl3)時(shí)等號(hào)成立.

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

5 結(jié)論

在現(xiàn)有國(guó)內(nèi)外專家對(duì)此問(wèn)題研究的基礎(chǔ)上，首先給出了單圈圖Steiner (n-1)-Wiener指標(biāo)的計(jì)算式；其次，確定了單圈圖Steiner (n-1)-Wiener指標(biāo)的上、下界，并刻畫了達(dá)到上、下界時(shí)的極圖，對(duì)下一步研究簡(jiǎn)單連通圖的Steinerk-Wiener指標(biāo)具有很好的借鑒意義.