段 蘭，余桂東，邢抱花

（安慶師范學院數(shù)學與計算科學學院，安徽安慶 246133）

給定懸掛點數(shù)圖的Wiener指數(shù)的極圖

段 蘭，余桂東，邢抱花

（安慶師范學院數(shù)學與計算科學學院，安徽安慶 246133）

設G是一個簡單圖，圖G的Wiener指數(shù)是G中所有頂點的距離之和。本文刻畫了給定頂點數(shù)和懸掛點數(shù)的圖類中，W iener指數(shù)取到最小、次小、第三小的極圖，并由此確定了關于懸掛點數(shù)的Wiener指數(shù)的下界。

圖；Wiener指數(shù)；懸掛點

設G（V（G），E（G））是一個簡單無向圖，V（G）為圖G的頂點集，E（G）為圖G的邊集。G中兩個頂點u，v之間的距離定義為G中連接u和v最短路的長度，記為dG（u，v）。圖G中任意兩點距離的最大值稱為G的直徑。圖G的Wiener指數(shù)，記作W（G），定義為圖G的所有點對的距離之和，即

Wiener指數(shù)廣泛應用于描述分子結構，它是于1947年由Harold Wiener作為路徑數(shù)目來引入的。Wiener根據(jù)化學中碳原子之間路徑距離的計數(shù)，提出了這個刻劃分子結構的指數(shù)，該指數(shù)等于碳氫化合物中所有最短碳-碳鍵路徑之和。有關Wiener指數(shù)的結構性質(zhì)可參閱［1］。

若用xi表示圖G中距離為i的頂點對個數(shù)，d為圖G的直徑，則Wiener指數(shù)也可表示為：

若圖G的直徑較小，則用（2）式來計算圖的Wiener指數(shù)較為方便［2］。但對于任意一個圖，若其直徑較大，我們很難給出每一個xi的確切值，因此對于某類圖，給出其Wiener指數(shù)的上界或下界是非常有意義的［3-4］。設M是具有n個頂點且懸掛點數(shù)為q的圖類，本文將給出圖類M中，Wiener指數(shù)取到最小、次小、第三小的唯一的圖，并由此確定了Wiener指數(shù)關于懸掛點的下界。

本文所獲主要結論如下。

設M是具有n個頂點，且懸掛點數(shù)為q的圖類。設B（n，q）是完全圖Kn-q上的頂點v1附著q個懸掛點的圖，B1（n，q）是完全圖Kn-q上頂點v1附著q個懸掛點且在Kn-q上刪去不與v1連接的一條邊的圖，B2（n，q）是完全圖Kn-q上頂點v1附著q-1個懸掛點且在另一頂點v2附上一個懸掛點的圖，或是完全圖Kn-q上在頂點v1附著q個懸掛點且在Kn-q上刪去均不與v1相連的兩條邊的圖，Bv1v2（n，q）是B（n，q）中刪去完全圖Kn-q中與頂點v1相連的一條邊v1v2所形成的圖是刪去中完全圖Kn-2的一條邊且該邊與頂點v1和v2都不相連的邊v3v4所得的圖。

引理1設圖G（V（G），E（G））是一個簡單無向圖，若邊uv?E（G），而點u，v∈V（G），圖G +uv表示圖G中添上不相鄰的邊uv所構成的圖，則W（G）＞W(wǎng)（G+uv）；若邊uv∈E（G），點u，v∈V（G），圖G-uv表示圖G中刪除邊uv所構成的圖，則W（G）＜W（G-uv）。

證明若圖G中邊uv?E（G），而點u，v∈V（G），則dG（u，v）＞1，而dG+uv（u，v）=1，所以dG（u，v）＞dG+uv（u，v）。而對于?u′，v′∈V（G），且｛u，v｝≠｛u′，v′｝時，都有dG（u′，v′）≥dG+uv（u′，v′），故由Wiener指數(shù)的定義知W（G）＞W(wǎng)（G+uv）。

同理可證，當邊uv∈E（G），點u，v∈V（G）時，W（G）＜W（G-uv）。

定理2B（n，q）是M中Wiener指數(shù)取到最小的唯一的圖，且?G∈M有

當且僅當G=B（n，q）時取等號。

證明設G1是圖類M中是由一個頂點數(shù)為n-q的圖G上系q個懸掛點所構成的圖，G2是完全圖Kn-q上系q個懸掛點的圖。若圖G不是完全圖Kn-q，由引理1知W（G1）＞W(wǎng)（G2）。

假設G2≠B（n，q），不妨設G2為完全圖Kn-q的i頂點v1，v2，…，vi（1≤i≤n-q）上分別系q1，q2，…，qi個懸掛點所構成的圖，且q=q1+q2+…+qi，則

故B（n，q）為圖類M中Wiener指數(shù)取到最小的唯一圖。

當且僅當G=B（n，q）時取等號。

定理3若q≤n-3（n≥4），則圖類M中Wiener指數(shù)取到次小的唯一圖：當q≠2時，為B1（n，q）；當q=2時，為B1（n，2）和B2（n，2），且當q≠2時，當且僅當G=B1（n，q）時取等號；當q=2時，當且僅當G=B1（n，2）或B2（n，2）時取等號。

證明由定理2知，B（n，q）是圖類M中W iener指數(shù)取到最小的唯一的圖。由引理1與圖類M的定義知，有兩種方法可以得到M中Wiener指數(shù)取到次小的圖：一是刪去B（n，q）中完全圖Kn-q中的一條邊（此q≥1時）；二是將B（n，q）中v1上的一個懸掛點移到其他頂點（如v2）上，此時要求q≥2。

方法1當q≥1時，刪去B（n，q）中完全圖Kn-q中的一條邊，得到的圖為B1（n，q）或Bv1v2（n，q）。

方法2當q≥2時，B（n，q）將中頂點v1上的一個懸掛點移到其他頂點（如v2）上所得的圖B2（n，q）。

當q=2時，W（B1（n，q））=W（B2（n，q）），即W（B1（n，2））=W（B2（n，2））。

當q＞2時，W（B1（n，q））＜W（B2（n，q））。

綜上所述，當q≠2時，圖類M中Wiener指數(shù)取到次小的唯一圖為B1（n，q）；當q=2時，圖類M中Wiener指數(shù)取到次小的圖為B1（n，2）或B2（n，2），且只有這兩個圖為次小圖。

定理4若q≤n-5（n≥6），則圖類M中Wiener指數(shù)取到第三小的圖：當q=1時，為Bv1v2（n，1），Bv4v51（n，1）和Bv3v41（n，1）；當q=2時，

證明由引理1、定理2、定理3及圖類M的定義知，圖類M中W iener指數(shù)取到第三小的圖可能在這三種圖中產(chǎn)生：一是B2（n，q）（q≥2）；二是Bv1v2（n，q）；三是在B1（n，q）上進行刪非懸掛邊或移懸掛點（移懸掛點時要求q≥2）所得的圖，且當q=2時，再加上第四種可能性，即在B2（n，2）上進行刪非懸掛邊所得的圖。

不妨設B1（n，q）是完全圖Kn-q中頂點v1上懸著q個懸掛點，在Kn-q上刪去不與v1連接的一條邊v2v3，且有非懸掛v4，v5點的圖。在圖B1（n，q）的基礎上進行刪非懸掛邊或移懸掛點有六種方法：一是刪去邊v1v2所得的圖，記為Bv1v21（n，q）；二是刪去邊v1v4所得的圖，記為Bv1v41（n，q）；三是刪去邊v4v5所得的圖，記為Bv4v51（n，q）；四是刪去邊v3v4所得的圖，記為Bv3v41（n，q）；五是將頂點v1上的1個懸掛點，移到頂點v2上所得的圖，記為六是將頂點v上的一個懸掛

1點，移到頂點v4上所得的圖，記為Bv41（n，q）（q≥2）。

（9）當q=2時，再加上第四種可能性，即在B2（n，2）上進行刪非懸掛邊所得的圖。不妨設B2（n，2）是完全圖Kn-p中頂點v1，v2上分別懸了1個懸掛點，且包含非懸掛點v3，v4的圖。由引理1知在B2（n，2）上有三種刪非懸掛邊的方法：一是刪去邊v1v3所得的圖，記為Bv1v32（n，2）；二是刪去邊v3v4所得的圖，記為Bv3v42（n，2）；三是刪去邊v1v2所得的圖，記為Bv2v32（n，2）。

［1］H.Wiener.Structural determination of paraffin boiling points［J］.J.Amer.Chem.Soc.，1947，69：17-20.

［2］湯自凱，鄭漢元.單圈圖的Wiener指數(shù)［D］.湖南師范大學，2007.

［3］湯自凱，鄭漢元.一類雙圈圖中具有最大、最小Wiener指數(shù)的圖［J］.湖南師范大學自然科學學報，2008，31：27-30.

［4］萬花，任海珍.一類三圈圖的Wiener指數(shù)［J］.數(shù)學研究，2012，45（2）：207-212.

［5］I.Gutman，J.H.Potgieter.Wiener index and intermolecular forces［J］.J.Serb.Chem.Soc.，1997，62：185-192.

［6］Dobrym in a Gutm，S.Klavzar，et al.Wiener index of hexagonal system s［J］.Acta App.Math.，2002，72：247-294.

［7］B.Zhou，X.Cai，N.Trinajstic.On reciprocal complementary Wiener number of trees［J］.Discrete Appl.Math.，2009，157：1628-1633.

［8］S.Nikolic，C.J.Trina.The Wiener index：developments and applications［J］.Groat.Chem.Acta.，1995，68：105-129.

［9］X.Qi，B.Zhou.Extremal properties of reciprocal complementary Wiener number of trees［J］.Computers and Mathematics with Applications，2011，62：523-531.

［10］H.Liu，M.Lu.A unified approach to extremal cacti for different indices［J］.MATCH Commun.Math.Comput.Chem.，2007，58：193-204.

ExtremalGraph of theWiener Index of Graphswith Given Number of Suspension Points

DUAN Lan，YU Gui-dong，XIN Bao-hua
（School of Mathematics and Computational Sciences，Anqing Teachers College，Anqing 246133，China）

Let be a simple graph，theWiener index of is the sum of distances between all pairs of vertices of.In this paper，we characterize the extremal graph with the first，the second and the third smallestWiener index among all graphswith given order and the number of suspension points，and give the lower bounds of the Wiener index of graphs with given number of suspension point.

graph，Wiener index，suspension point

O157.5

A

1007-4260（2014）03-0028-04

時間：2014-9-15 16：07 網(wǎng)絡出版地址：http：//www.cnki.net/kcms/doi/10.13757/j.cnki.cn34-1150/n.2014.03.008.html

2014-02-26

安徽省自然科學基金（11040606M14），安徽省高校自然科學重點項目基金（KJ2011A195，KJ2013A196）和安慶師范學院青年科學研究基金（KJ201307）資助。

段蘭，女，安徽太湖人，安慶師范學院數(shù)學與計算科學學院碩士研究生，研究方向為圖論及其應用。