邢 抱 花

(安庆师范学院 数学与计算科学学院，安徽 安庆 246133)



两类粘合图的Wiener与Harary指数

邢 抱 花

(安庆师范学院 数学与计算科学学院，安徽 安庆 246133)

摘要：连通图G的Wiener指数是指图G中所有点对的距离之和，Harary指数是指图G中所有点对的距离的倒数之和。本文主要研究了单圈图与双圈图的粘合图以及双圈图与双圈图的粘合图的Wiener指数的下界和Harary指数的上界的问题，并刻画了对应的极值图。

关键词：单圈图；双圈图；粘合；Wiener指数；Harary指数

连通图G的Wiener指数与Harary指数是两个很重要的拓扑参数，它们与分子的物理、化学性质有一定的联系，对它们进行研究有很重要的意义。Wiener指数是在1947年由美国化学家H.Wiener首次提出的，Harary指数是在1993年由Plavsic′和Ivanciuc等在刻划分子结构图时各自独立提出的。这两种拓扑指数各自被提出之后，许多学者对它们进行了大量的研究[2-10]。其中文献[2]与文献[3]分别解决了n阶单圈图和n阶双圈图的Wiener指数的下界问题。文献[5]给出了n阶单圈图和n阶双圈图的Harary指数的上界以及相应的极图。本文主要研究了单圈图与双圈图的粘合图、双圈图与双圈图的粘合图的Wiener指数的下界和Harary指数的上界，并刻画了对应的极值图。这些结论，对于探讨三圈图或四圈图的Wiener指数的下界与Harary指数的上界以及对应的极值图有帮助。

文中所涉及的图都是有限的无向简单连通图。对于连通图G，记它的顶点集和边集分别为V(G),E(G)，它的阶数(即顶点个数)与边数分别记为|V(G)|,|E(G)|。若|E(G)|=|V(G)|，则图G为单圈图；若|E(G)|=|V(G)|+1，则图G为双圈图。设图G1与G2是两个连通图，且V(G1)∩V(G2)={v}，把图G1中的顶点v与图G2中的顶点v粘合为一个点后得到的新图G，称为图G1与G2的粘合图，记作G=G1vG2。连通图G中两顶点u,v的距离是指连接u,v的最短路的长度，记为dG(u,v)。∀v∈V(G)，v的距离是指图G中其余顶点到顶点v的距离之和，记为DG(v)。连通图G的Wiener指数是指图G中所有点对的距离之和，记为W(G)；Harary指数是指图G中所有点对的距离的倒数之和，记为H(G)，即

连通图G中顶点u的度是指与顶点u关联的边数，记为d(u)。若d(u)=1，则称顶点u为悬挂点。在n阶星图Sn的两个悬挂点间添加一条边e后得到的新图，记为Sn+e。在星图Sn上添加两条边e1,e2后得到的新图分别记为Sn+e1+e2,Sn+(e1+e2)，其中新图Sn+(e1+e2)中添加的两条边e1,e2有公共顶点。文中没有被定义的其他术语，读者可参看文献[1]。

引理1[2]设μ1(n)表示n阶单圈图的全体，G∈μ1(n)，则W(G)≥n2-2n，等号成立当且仅当G为Sn+e。

引理2[3]设μ2(n)表示n阶双圈图的全体，G∈μ2(n)，则W(G)≥n2-2n-1，等号成立当且仅当G为Sn+e1+e2或G为Sn+(e1+e2)。

引理3[4]设H1,H2是连通图G的两个连通子图，且V(H1)∩V(H2)={v},令G=H1vH2，则W(G)=W(H1)+W(H2) +(|V(H1)|-1)DH2(v)+(|V(H2)|-1)DH1(v)。

引理6[6]设G1，G2是连通图G的两个连通分支，V(G1)∩V(G2)={v}，令G=G1vG2，则

H(G)=H(G1)+H(G2) +

定理1设G1为s阶的一个单圈图，G2为t阶的一个双圈图，s+t=n+1且V(G1)∩V(G2)={v},令G=G1vG2,则

等号成立当且仅当图G为G1(n,n-7)或为G2(n,n-6)(如图1 所示)。

证明由引理3和引理6知，

W(G)=W(G1)+W(G2) +(|V(G1)|-1)DG2(v)+(|V(G2)|-1)DG1(v)

H(G)=H(G1)+H(G2) +

W(G)=W(G1)+W(G2) +(|V(G1)|-1)DG2(v)+(|V(G2)|-1)DG1(v)≥

s2-2s+t2-2t-1+(s-1)(t-1)+(t-1)(s-1)=

(s+t)2-4(s+t)+1=

(n+1)2-4(n+1)+1=n2-2n-2

H(G)=H(G1)+H(G2) +

等号成立当且仅当G是图1中图G1(n,n-7)或为G2(n,n-6)。

图2图H1(n,n-9),H2(n,n-8)与H3(n,n-7)

定理2设G1,G2分别是s,t阶的连通双圈图，s+t=n+1且V(G1)∩V(G2)={v}，令G=G1vG2,则

等号成立当且仅当图G为H1(n,n-9)或G为H2(n,n-8)或G为H3(n,n-7)。(如图2所示)

证明由引理2和引理5知，

W(G1)=s2-2s-1,W(G2)=t2-2t-1,

等号成立当且仅当图G1为Ss+e1+e2或Ss+(e1+e2)，图G2为St+e1+e2或St+(e1+e2)。

等号成立当且仅当v是图G1=Ss+e1+e2,G2=St+e1+e2中度最大的顶点或v是图G1=Ss+(e1+e2),G2=St+(e1+e2)中度最大的顶点或v是图G1=Ss+e1+e2,G2=St+(e1+e2)中度最大的顶点。

再由引理3和引理6知，

W(G)=W(G1)+W(G2) +(|V(G1)|-1)DG2(v)+(|V(G2)|-1)DG1(v)

H(G)=H(G1)+H(G2) +

故

W(G)=W(G1)+W(G2) +(|V(G1)|-1)DG2(v)+(|V(G2)|-1)DG1(v)≥

s2-2s-1+t2-2t-1+

(s-1)(t-1)+(t-1)(s-1)=

(s+t)2-4(s+t)=

(n+1)2-4(n+1)=n2-2n-3

H(G)=H(G1)+H(G2) +

等号成立当且仅当图G为H1(n,n-9)或G为H2(n,n-8)或G为H3(n,n-7)。(如图2所示)

参考文献:

[1] Bondy A, Mmurty U S R. Graph Theory with Application[M]. New York: Macmillan Press, 1976.

[2] 汤自凯. 单圈图的Wiener指数[D]. 长沙：湖南师范大学，2006.

[3] 邵云，邢抱花. 具有最小Wiener指数的双圈图[J]. 安庆师范学院学报(自然科学版)，2009，15(3)：8-12.

[4] Dobryin A A, Entringer R, Gutman I. Wiener index of trees: Theory and Application[J]. Acta Appl Math,2001(66)：211-249.

[5] K.Xu, K.C.Das. Extremal Unicyclic and Bicyclic Graphs with Respect to Harary Index[J]. Bull.Malays.Math.Sci.Soc(2), 2013，36(2)：373-383.

[6] K.Xu, N.Trinajstic. Hyper-Wiener and Harary indices of graphs with cut edges[J]. Util.Math.,2011 (84)：153-163.

[7] G. Yu, L. Feng. On the maximal Harary index of a class of bicyclic graphs[J]. Util. Math.,2010 (82)： 285-292.

[8] B. Zhou, X. Cai, N. Trinajstic. On the Harary index[J]. J. Math. Chem.,2008 (44)：611-618.

[9] K. Xu, K. C. Das. On Harary index of graphs[J]. Discr. Appl. Math.,2011 (159)：1631-1640.

[10] T. Doˇslic, M. Ghorbani, M. A. Hosseinzadeh. The relationships between Wiener index, stability number and clique number of composite graphs[J]. Bull. Malays. Math. Sci. Soc.(2)，2013，36(1)：165-172.

Wiener Index and Harary Index of Two Classes Graphs from Identification

XING Bao-hua

(School of Mathematical & Computational Science, Anqing Teachers College, Anqing 246133, China)

Abstract:The Wiener index of a graph G is defined as the sum of distances over all pairs of vertices and the Harary index of a graph G is defined as the sum of reciprocals of distances over all pairs of vertices. In this paper, we give a lower bound for the Wiener index and a upper bound for the Harary index of G, the graph G is constructed by identifying a vertex v1of a unicyclic graph G1and a vertex v2of a bicyclic graph G2, or the graph G is constructed by identifying a vertex v1of a bicyclic graph G1and a vertex v2of a bicyclic graph G2.

Key words:unicyclic graph, bicyclic graph, identify, Wiener index, Harary index

文章编号：1007-4260(2015)02-0001-03

中图分类号：O157.5

文献标识码：A

作者简介：邢抱花，女，安徽当涂人，硕士，安庆师范学院数学与计算科学学院讲师，研究方向为图论。

基金项目：安庆师范学院青年科研基金(KJ201309)。

收稿日期：2015-02-05