兩類粘合圖的Wiener與Harary指數

邢 抱 花

(安慶師范學院 數學與計算科學學院，安徽 安慶 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