蘇曉海

(陜西理工學院 數學與計算機科學學院， 陜西 漢中 723000)

?

一類直徑可以任意大的雙圈圖及其線圖的Wiener指標

蘇曉海

(陜西理工學院 數學與計算機科學學院， 陜西 漢中 723000)

[摘要]一個連通圖G的Wiener指標是指G中所有頂點對之間距離的總和，即。研究了一類直徑可以任意大的雙圈圖Gr，t的Wiener指標，證明了Gr，t滿足性質W(Gr，t)=W(L(Gr，t))，其中L(Gr，t)表示圖Gr，t的線圖。

[關鍵詞]Wiener指標；雙圈圖；線圖

在最近的40年里，Wiener指標的數學性質和化學應用都得到了深入研究。如今，Wiener指標是一個最好理解和最常用的分子模型描述符。在模擬物理化學、藥理及生物學特性的有機分子方面，發(fā)現Wiener指標有許多應用[2-8]。有兩組密切相關的問題，已經引起了研究者很長一段時間的關注：Wiener指標如何依賴于一個圖的結構和Wiener指標如何隨著圖形的變形而變化？在數學化學研究中有趣的方法之一是用參數計算來刻畫分子圖的派生結構。線圖可以較好地反映原圖的分枝，這是一個導出分子圖形結構很好的例子。線圖的這種不變性已經被用于評價結構復雜的分子圖形、結構排序和設計新穎的拓撲指數[9-12]。

本文主要研究并找出滿足下列性質:

(1)

且有規(guī)定的圈數λ=2的圖。在文獻[8]中已經表明，樹(λ=0)及其線圖的Wiener指數總是不同的。對于單圈圖，除了簡單的圈圖之外，均滿足W(L(G))

引理1[2,12]設圖G是由圖G1的一個頂點u和G2的一個頂點v重合到一起組成的，則

(2)

其中dG1(u)表示從頂點u到圖G1的所有頂點的距離之和，而dG2(v)表示從頂點v到圖G2的所有頂點的距離之和。

引理2[2]設Pn和Sn分別是階為n的路和星圖，則

引理3[2]設Tn是階為n的樹，則W(Sn)≤W(Tn)≤W(Pn)。

考慮圖Gr，t，具體結構見圖1。通過構造，它是圈數為λ=2，階為2r+t+5的圖，其直徑d=r+t+3，對于每一組r和t，當r和t無限增大時，直徑d也無限增大，其線圖L(Gr，t)的具體結構見圖2。圖Gr，t和L(Gr，t)的子圖見圖3—圖4。

圖1　圖Gr，t

圖2　Gr，t的線圖L(Gr，t)

圖3　Gr，t的子圖T和G1

圖4　L(Gr，t)的子圖G2和G3

證明因為[14]

其中圖G的頂點個數(階)記為nG。由W(G1)=14，nG1=5，dG1(u)=4，和引理1，有

于是，得到如下結論：

其中k≥6是任意自然數。下面只需要說明r一定是正整數即可：由于k和k-5兩個整數必有一個是偶數，所以r一定是正整數。定理得證。

[參考文獻]

[1]WIENER H.Structural determination of paraffin boiling points[J].Journal of the American Chemical Society,1947,69(1):17-20.

[2]DOBRYNIN A A,ENTRINGER R,GUTMAN I.Wiener index of trees:theory and applications[J].Acta Appl Math,2001(66):211-249.

[3]DOBRYNIN A A,GUTMAN I,Klav?ar S,et al.Wiener index of hexagonal systems[J].Acta Appl Math,2002(72):247-294.

[4]Nikolié S,Trinajstié N,Mihalié Z.The Wiener index:developments and applications[J].Croat Chem Acta,1995(68):105-129.

[5]BERTZ S H,WRIGHT W F.The graph theory approach to synthetic analysis:definition and application of molecular complexity and synthetic complexity[J].Graph Theory Notes,1998(35):32-48.

[6]ESTRADA E,GUEVARA N,GUTMAN I.Extension of edge connectivity index Relationships to line graph indices and QSPR applications[J].Journal of Chemical Information and Modeling,1998,38(3):428-431.

[7]GUTMAN I,ESTRADA E.Topological indices based on the line graph of the molecular graph[J].Journal of Chemical Information and Modeling,1996,36(3):541-543.

[8]BUCKLEY F.Mean distance of line graphs[J].Graph Theory and Computing,1981,1(32):153-162.

[9]GUTMAN I.Distance of line graphs[J].Graph Theory Notes,1996(31):49-52.

[10]GUTMAN I,Pavlovié L.More on distance of line graphs[J].Graph Theory Notes,1997(33):14-18.

[11]DOBRYNIN A A,GUTMAN I,Jova?evié V.Bicyclic graphs and its line graphs with the same Wiener index[J].Diskretn.Analiz Issled.Oper Ser,1997,4(2):3-9.

[12]DOBRYNIN A A,Mel’nikov L S.Wiener index,line graphs and the cyclomatic number[J].MATCH Communications in Mathematical and in Computer Chemistry,2005,53(1):209-214.

[13]DOBRYNIN A A,Mel’nikov L S.Wiener index for graphs and their line graphs with arbitrary large cyclomatic numbers[J].Applied Mathematics Letters,2005,18(3):307-312.

[14]鄧漢元.一類化學圖及其線圖的Wiener指數[J].湖南師范大學：自然科學學報,2009,32(3):23-26.

[責任編輯：謝 平]

2015年12月陜西理工學院學報(自然科學版)

Bicyclic graphs and Wiener index of their line graphs for arbitrarily

large diameter

SU Xiao-hai

(School of Mathematics and Computer Science, Shaanxi University of Technology,

Hanzhong 723000, China)

Abstract:The Wiener index of a connected graph G is the sum of distance between all unordered pairs of vertices in G, that is d(u,v). The paper studies Wiener index of bicyclic graphs Gr,twhich has arbitrarily large diameter. It proves that Gr,tmeets the properties W(Gr,t)=W(L(Gr,t)), whereL(Gr,t)is the line graphs of Gr,t.

Key words:Wiener index；bicyclic graph；line graph

作者簡介：蘇曉海(1979—)，男，云南省普洱市人，陜西理工學院講師，碩士，主要研究方向為圖論及其應用。

基金項目：陜西省教育廳科學研究計劃項目(15JK1143)

收稿日期：2015-03-29

[中圖分類號]O157.5

[文獻標識碼]A

[文章編號]1673-2944(2015)06-0057-03