許冬冬， 高煒

(云南師范大學(xué) 信息學(xué)院,云南 昆明 650500)

在理論化學(xué)中，常用圖模型來表示分子結(jié)構(gòu)，用頂點來表示原子，邊表示它們之間的化學(xué)鍵.而化學(xué)分子的特性常常用一些參數(shù)來衡量，比如PI指數(shù)、維納指數(shù)、Randic指數(shù)等等[1-5].本文只考慮無向、簡單、有限圖.設(shè)G是一個圖，它的頂點集合和邊集分別用V(G)和E(G)來表示.文中所用符號和標(biāo)記若沒有特別說明則與文獻[6]一致.

一個圖的維納指數(shù)W(G)是圖中所有頂點對的距離之和：

其中d(u,v)表示頂點u和v在G中的距離.超維納指數(shù)WW(G)作為一般維納指數(shù)的推廣，其定義如下：

有關(guān)超維納指數(shù)的研究是近年來理論化學(xué)研究的熱點[7-10].本文將研究線圖和一些特殊圖類的超維納指數(shù)，給出若干結(jié)果.

1 線圖的超維納指數(shù)

定理1 設(shè)G是有n個頂點，m條邊的連通圖，且頂點vi的度為di.若G的直徑Diam(G)≤2且G的任意一個導(dǎo)出子圖都不同構(gòu)于下面的F1、F2和F3.

圖1 G的導(dǎo)出子圖的禁圖

設(shè)L(G)為G的線圖，則有：

(1)

對一個直徑不超過2的連通圖，易知在導(dǎo)出子圖不同構(gòu)于F1、F2和F3的條件下，其線圖的直徑也不會超過2.從而有

結(jié)論證畢.

推論1 設(shè)G是一個有n個頂點的連通r正則圖.若G的直徑Diam(G)≤2且G的任意一個導(dǎo)出子圖都不同構(gòu)于圖1中的F1、F2和F3.則有

定理2 設(shè)G是一個連通圖，其頂點集合V(G)={v1,v2,…,vn},邊集合E(G)={e1,e2,…,em}.設(shè)vi的度為di.若e=uv是G的任意一條邊，則e的度定義為d(e)=du+dv-2.則有

上式等號成立的充分必要條件為：G的直徑Diam(G)≤2且G的任意一個導(dǎo)出子圖都不同構(gòu)于圖1中的F1、F2和F3.

對于邊e=uv，它一共關(guān)聯(lián)了d(e)=du+dv-2條邊.因此e在G中不關(guān)聯(lián)的邊共有m-1-d(e)條.在L(G)中，e與這m-1-d(e)個頂點的距離至少為2.從而有

若G的直徑Diam(G)≤2且G的任意一個導(dǎo)出子圖都不同構(gòu)于圖1中的F1、F2和F3，則Diam(L(G))≤2成立.e與這m-1-d(e)個頂點在L(G)中的距離恰好為2，從而

(2)

反過來要使(2)成立，那么G中任意兩條不關(guān)聯(lián)的邊在L(G)中的距離必須為2.設(shè)ei和ej在L(G)中的距離為2，則存在G中的邊ek同時與ei和ej關(guān)聯(lián).這時G的任意一個導(dǎo)出子圖都不同構(gòu)于圖1中的3個禁圖，且Diam(G)≤2.結(jié)論證畢.

推論2 設(shè)G是一個有n個頂點的連通r正則圖.則

上式等號成立的充分必要條件為：G的直徑Diam(G)≤2且G的任意一個導(dǎo)出子圖都不同構(gòu)于圖1中的F1、F2和F3.

下面兩個定理討論樹的線圖的超維納指數(shù)計算公式.

定理3 設(shè)T是一個樹，V(T)={v1,…,vn}且vi的度記為di(i=1,2,…,n).L(T)表示T的線圖，則

證明線圖L(T)的頂點即為原圖T的邊.對于每個頂點vi而言，有di條邊和它相關(guān)聯(lián)，這些邊在L(T)中構(gòu)成頂點數(shù)為di的完全圖.因此這di個頂點之間的距離和以及距離平方和均為

(3)

設(shè)vi、vj是T中的頂點，它們的度分別為di、dj.設(shè)x1、x2、…、xdi-1是頂點vi在T中所關(guān)聯(lián)的邊，y1、y2、…、ydj-1是頂點vj在T中所關(guān)聯(lián)的邊，且滿足xl和yk沒有公共頂點(1≤l≤di-1,1≤k≤dj-1), 同時這些邊都不在vi、vj之間的路徑上.由此可知xl和yk在L(T)中的距離為1+d(vi,vj).從而關(guān)聯(lián)vi的邊x1、x2、…、xdi-1和關(guān)聯(lián)vj的邊y1、y2、…、ydj-1之間的距離和以及距離平方和分別為：

[1+d(vi,vj)](di-1)(dj-1)

(4)

[1+d(vi,vj)]2(di-1)(dj-1)

(5)

結(jié)合(3)-(5)，可知

結(jié)論證畢.

定理4 設(shè)T是一個樹，有k個度為s的頂點，其他頂點度均為1.T′是在T中刪除所有終端頂點后得到的樹.則

證明對于i=1,2,…,k, 設(shè)vi的度為s；而對于i=k+1,k+2,…,n,記vi的度為1.從而對于i,j=k+1,k+2,…,n，有di-1=dj-1=0.根據(jù)定理3的結(jié)果，可得

結(jié)論證畢.

2 若干圖類的超維納指數(shù)

定理5 設(shè)G是有n個頂點的連通圖，并包含團Kk.設(shè)G(n,k)為在G中刪除Kk的邊得到的圖，0≤k≤n-1.則有

等式成立當(dāng)且僅當(dāng)G?Kn.

證明設(shè)V(G)={v1,v2,…,vn}.不失一般性，設(shè)團Kk的頂點集為S1={v1,v2,…,vk}，G中剩下的頂點為{vk+1,vk+2,…,vn}.從而S1中任意兩個頂點在G(n,k)中的距離至少為2，剩余頂點對在G(n,k)中的距離至少為1.得到

若G?Kn，則可直接驗證上式等號成立.

設(shè)G1、G2是G的兩個子圖.若|V(G1)∩V(G2)|=0成立，則稱G1、G2是獨立的.

結(jié)論證畢.

定理7 設(shè)ei(其中i=1,2,…,k,0≤k≤n-2)是完全圖Kn中與某個頂點v相關(guān)聯(lián)的k條邊.設(shè)Kn(k)是從Kn中刪除邊ei(i=1,2,…,k)得到的圖.則有

結(jié)論證畢.

參 考 文 獻:

[1] YAN L,LI Y,GAO W,et al.PI index for some special graphs[J].Journal of Chemical and Pharmaceutical Research,2013,5(11):260-264.

[2] GAO W,SHI L.Wiener index of gear fan graph and gear wheel graph[J].Asian Journal of Chemistry,2014,26(11):3397-3400.

[3] GAO Y,LIANG L,GAO W.Eccentric connectivity index of some special molecular graphs and theirr-corona graphs[J].International Journal of Chemical and Process Engineering Research,2014,1(5):43-50.

[4] GAO Y,LIANG L,GAO W.Randic index and edge eccentric connectivity index of certain special molecular graphs[J].International Journal of Chemistry and Materials Research,2014,2(8):81-87.

[5] XI W,GAO W.Geometric-arithmetic index and Zagreb indices of certain special molecular graphs[J].Journal of Advances in Chemistry,2014,10(2):2254-2261.

[6] BONDY J A,MURTY U S R.Graph theory with applications[M].London:Macmillan Press,1976.

[7] YAN L,LI Y,GAO W,et al.On the extremal hyper-wiener index of graphs[J].Journal of Chemical and Pharmaceutical Research,2014,6(3):477-481.

[8] DOU J,WANG Y,GAO W.Some characteristics on hyper-wiener index of graphs[J].Journal of Chemical and Pharmaceutical Research,2014,6(5):1659-1663.

[9] PAN Y.Wiener number and hyper-wiener number of two types of polyomino systems[J].Journal of Mathematical Study,2013,46(3):260-269.

[10]CASH G.Three methods for calculation of the hyper-wiener index of molecular graphs[J].Journal of Chemical Information and Computer Science,2002,42,571-576.