蘇曉海

(陜西理工學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院， 陜西 漢中 723000)

?

一類直徑可以任意大的雙圈圖及其線圖的Wiener指標(biāo)

蘇曉海

(陜西理工學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院， 陜西 漢中 723000)

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

[關(guān)鍵詞]Wiener指標(biāo)；雙圈圖；線圖

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

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

(1)

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

引理1[2,12]設(shè)圖G是由圖G1的一個(gè)頂點(diǎn)u和G2的一個(gè)頂點(diǎn)v重合到一起組成的，則

(2)

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

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

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

考慮圖Gr，t，具體結(jié)構(gòu)見圖1。通過構(gòu)造，它是圈數(shù)為λ=2，階為2r+t+5的圖，其直徑d=r+t+3，對(duì)于每一組r和t，當(dāng)r和t無(wú)限增大時(shí)，直徑d也無(wú)限增大，其線圖L(Gr，t)的具體結(jié)構(gòu)見圖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

證明因?yàn)閇14]

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

于是，得到如下結(jié)論：

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

[參考文獻(xiàn)]

[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]鄧漢元.一類化學(xué)圖及其線圖的Wiener指數(shù)[J].湖南師范大學(xué)：自然科學(xué)學(xué)報(bào),2009,32(3):23-26.

[責(zé)任編輯：謝 平]

2015年12月陜西理工學(xué)院學(xué)報(bào)(自然科學(xué)版)

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

作者簡(jiǎn)介：蘇曉海(1979—)，男，云南省普洱市人，陜西理工學(xué)院講師，碩士，主要研究方向?yàn)閳D論及其應(yīng)用。

基金項(xiàng)目：陜西省教育廳科學(xué)研究計(jì)劃項(xiàng)目(15JK1143)

收稿日期：2015-03-29

[中圖分類號(hào)]O157.5

[文獻(xiàn)標(biāo)識(shí)碼]A

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