一类直径可以任意大的双圈图及其线图的Wiener指标

苏晓海

(陕西理工学院 数学与计算机科学学院， 陕西 汉中 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指标是一个最好理解和最常用的分子模型描述符。在模拟物理化学、药理及生物学特性的有机分子方面，发现Wiener指标有许多应用[2-8]。有两组密切相关的问题，已经引起了研究者很长一段时间的关注：Wiener指标如何依赖于一个图的结构和Wiener指标如何随着图形的变形而变化？在数学化学研究中有趣的方法之一是用参数计算来刻画分子图的派生结构。线图可以较好地反映原图的分枝，这是一个导出分子图形结构很好的例子。线图的这种不变性已经被用于评价结构复杂的分子图形、结构排序和设计新颖的拓扑指数[9-12]。

本文主要研究并找出满足下列性质:

(1)

且有规定的圈数λ=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