具有給定圍長單圈圖的　Harary指數(shù)的最大值*

陳單單

（湖南財經工業(yè)職業(yè)技術學院公共課部，湖南，衡陽，421002）

具有給定圍長單圈圖的Harary指數(shù)的最大值*

陳單單

（湖南財經工業(yè)職業(yè)技術學院公共課部，湖南，衡陽，421002）

本文首先給出了單圈圖的Harary指數(shù)的一種計算方法，然后利用這一方法給出了具有給定圍長單圈圖的Harary指數(shù)的最大值，以及對應的極圖.

圍長 單圈圖 Harary指數(shù) 反距離

1　引言

拓撲指數(shù)是從化合物的結構圖衍生出來的一種數(shù)學不變量.大約在一百多年之前就引入了拓撲指數(shù)，至今已有200多種被證實在結構-活性/性質相關性（QSAR/QSPR）中非常有用，這些指數(shù)中有些是基于圖中點的距離，有些是基于圖中點的度數(shù).而Harary指數(shù)是基于圖中點的距離.

在1993年，Plav?iC等［1］和Ivanciuc等［2］各自獨立提出了Harary指數(shù)模型來刻劃分子結構圖.設G=（V，E）是一個簡單的連通圖，其中V和E分別為G的頂點集和邊集，則圖G的Harary指數(shù)定義為

Diudea［3］對路、圈、星圖的Harary指數(shù)進行了計算，給出了一些有意義的結論，并通過對這些圖的Harary指數(shù)可達或不可達值的分析，得出Harary指數(shù)對刻畫分子結構圖意義十分重大.Harary指數(shù)與Wiener指數(shù)都是基于圖中點的距離，由于在許多情況下，原子之間距離較遠的影響小于與其相鄰的原子，在描述分子結構圖時，Harary指數(shù)優(yōu)于Wiener指數(shù)［4］，并使分子的結構屬性得到改善［5］.有關Harary指數(shù)有許多有趣的屬性，以及與其它距離拓撲指數(shù)的關系見［6-15］.

本文首先給出了單圈圖的Harary指數(shù)的一種計算方法，然后利用這一方法給出了給定圍長單圈圖的Harary指數(shù)的最大值，以及對應的極圖.

2　單圈圖的Harary指數(shù)的計算

本文所涉及的圖都是連通的簡單無向圖.設G=（V，E）是頂點集和邊集分別是V和E的圖，G 的頂點數(shù)用n（G）表示，稱為G 的階.頂點u與v之間的距離dG（u，v）（或d（u，v））是指G中連接頂點u與v之間的最短路徑的長度.圖G的Harary指數(shù)定義為

若G=（V，E）是一個n階單圈圖，其中的圈Cm=v1v2…vmv1的長度為m （即圍長）且m≤n ，則G-E（Cm）的連通分支Ti（i=1，2，…，m）都是樹，Ti與Cm的公共頂點為vi，這樣的單圈圖我們用G=U（Cm；T1，T2，…，Tm）表示.令n（Ti）=li+1，則l=l1+l2+…+lm= n-m.特別地，若Ti=Sli+1是以vi為中心的li+1階星圖，則G=U（Cm；T1，T2，…，Tm）= U（Cm；Sl1+1，Sl2+1，…，Slm+1）；若Ti=Pli+1是以vi為其中一個端點的li+1階路，則G= U （Cm；T1，T2，…，Tm）=U （Cm；Pl1+1，Pl2+1，…，Plm+1）.

為了計算n階單圈圖G的Harary指數(shù)，我們需要了解有關樹的Harary指數(shù)的結果.

引理1［15］ 設T是任意不同于星圖Sn與路Pn的n階樹，則

關于圈的Harary指數(shù)，我們很容易證明下面的結論：

引理2 設Cn是n階單圈圖，則

下面我們給出關于單圈圖Harary指數(shù)的一個計算方法.

定理3 設G=U（Cm；T1，T2，…，Tm）是一個n階單圈圖，則

證明 我們將圖G的頂點之間的反距離分為四類：（i）兩個頂點都在圈Cm上；（ii）兩個頂點中一個在圈Cm上，另一個在某Ti-｛vi｝上；（iii）兩個頂點都在同一個Ti-｛vi｝上；（iv）兩個頂點中一個在Ti-｛vi｝，另一個在Tj-｛vj｝上（i≠j）.

（i）設兩個頂點都在圈Cm上的反距離之和為H1，則

（ii）設兩個頂點中一個在圈Cm上，另一個在某Ti-｛vi｝上的反距離之和為H2，則

（iii）設兩個頂點都在同一個Ti-｛vi｝，i=1，2，…，m上的反距離之和為H3，則

（iv）設兩個頂點中一個在Ti-｛vi｝，另一個在Tj-｛vj｝，（i≠j）的反距離之和為H4.?x∈Ti-｛vi｝，?y∈Tj-｛vj｝，則

于是，Ti-｛vi｝與Tj-｛vj｝中頂點之間的反距離之和為

因此，

從而

3　給定圍長的單圈圖的最大Harary指數(shù)

這一節(jié)我們首先給出具有給定圍長m（3≤m≤n）的單圈圖的Harary指數(shù)的界，然后刻劃出具有給定圍長的單圈圖G中具有最大Harary指數(shù)的圖的特征.

定理4 設G=U（Cm；T1，T2，…，Tm）是一個n階單圈圖，Ti是li+1階的樹，i=1，2，…，m，則有

H （U （Cm；Pl1+1，Pl2+1，…，Plm+1））≤H （G ）≤H （U （Cm；Sl1+1，Sl2+1，…，Slm+1））.

左等號成立當且僅當G?U（Cm；Pl1+1，Pl2+1，…，Plm+1），而右等號成立當且僅當G?U （Cm；Sl1+1，Sl2+1，…，Slm+1）.

證明 由引理1知，H （Pli+1）≤H （Ti）≤H （Sli+1）且左等號成立當且僅當Ti?Pli+1，vi是Pli+1的一個端點；右等號成立當且僅當Ti?Sli+1，vi是Sli+1的中心，i=1，2，…，m.設V（Ti）-｛vi｝=V（Sli+1）-｛vi｝=｛y1，y2，…，yli｝，Pli+1=viy1y2…yli.不妨設在Ti中y1，y2，…，yli到vi的距離是不減的，即dTi（vi，y1）≤dTi（vi，y2）≤…≤dTi（vi，yli），則

因為

而

因此，對于x ∈Cm，有

和

同樣地，有

由定理3得

H（U （Cm；Pl1+1，Pl2+1，…，Plm+1））≤H（G ）≤H（U （Cm；Sl1+1，Sl2+1，…，Slm+1）），

左等號成立當且僅當G?U（Cm；Pl1+1，Pl2+1，…，Plm+1）；右等號成立當且僅當G?U（Cm；Sl1+1，Sl2+1，…，Slm+1）.

由上述結論，我們現(xiàn)在可以給出具有給定圍長的單圈圖中具有最大Harary指數(shù)的特征.

定理5 設G=U（Cm；T1，T2，…，Tm）是任意一個圍長為m單圈圖，則

等號成立當且僅當G?U（Cm；Sn-m+1，S1，…，S1），即U（Cm；Sn-m+1，S1，…，S1）是圍長為m的n階單圈圖中唯一具有最大Harary指數(shù)的圖.

證明 由定理4

下面證明：

因此，H（U（Cm；Sn-m+1，S1，…，S1））≥H（G）等號成立當且僅當l2=0，即

利用定理3，我們可計算出兩個圍長分別m和m-1為的n階單圈圖U（Cm；Sn-m+1，S1，…，S1）和U（Cm-1；Sn-m+2，S1，…，S1）的Harary指數(shù)，直接比較可得n 階單圈圖的Harary指數(shù)的最大值.

［1］PlavsiC，D.&S.NikoliC&N.TrinajstiC&Z.MihaliC.On the Harary index for the characterization of chemical graphs［J］.J.Math.Chem.1993，（12）：235-250.

［2］Ivanciuc，O.&T.S.Balaban&A.T.Balaban.Reciprocal distance matrix，related local vertex invariants and topological indices［J］.J.Math.Chem.1993，（12）：309-318.

［3］Diudea，M.V.Indices of reciprocal properties or Harary indices［J］.J.Chem.Inf.Comput.Sci.1997，（37）：292-299.

［4］Lucic，B.&A.Milicevic&S.Nikolic&N.Trinajstic.Harary index-twelve years later［J］.Croat.Chem. Acta，2002，（75）：847-868.

［5］Trinajstic，N.&S.Nikolic&S.C.Basak&I.Lukovits.Distance indices and the their hyper-counterparts：Intercorrelation and use in the structure-property modeling［J］.SAR QSAR Environ.Res.2001，（12）：31-54.

［6］Ivanciuc，O.&T.Ivanciuc&A.T.Balaban.Design of topological indices.Part 10.Parameters based on electronegativity and vovalent radius for computation of molecular graph descriptors for heteroatom-containing molecules［J］.J.Chem.Inf.Comput.Sci.1998，（38）：395-401.

［7］Zhou，B.&X.Cai&N.Trinajstic.On Harary index［J］.J.Math.Chem.2008，（44）：611-618.

［8］Das，K.Ch.&B.Zhou&N.Trinajstic.Bounds on Harary index［J］，J.Math.Chem.2009，46：1369 -1376.

［9］Zhou，B.&Z.Du&N.Trinajstic.Harary index of landscape graphs［J］.Int.J.Chem.Model.2008，（1）：35-44.

［10］Gutman，I.A property of the Wiener number and its modifications［J］.Indian J.Chem.1997，（36A）：128-132.

［11］Zhou，B.&I.Gutman.Relationships between Wiener，hyper-Wiener and Zagreb indices［J］.Chem. Phys.Lett.2004，（394）：93-95.

［12］Zhou，B.&N.Trinajstic.On the maximum eigenvalues of the reciprocal distance matrix and the reverse Wiener matrix［J］.Int.J.Quantum Chem.2008，（108）：858-864.

［13］Ivanciuc，O.&T.S.Balaban&A.T.Balaban.Reciprocal distance matrix，related local vertex invariants and topological indices［J］.J.Math.Chem.1993，（12）：309-318.

［14］Das，K.C.&K.Xu&I.N.Cangul&A.S.Cevik&A.Graovac，On the Harary index of graph operations［J］.Journal of Inequalities and Applications.2013，2013：339.

［15］Xu，K.&K.H.DAS.Extremal unicyclic and bicyclic graphs with respect to Harary index［J］.Bull.Ma

lays.Math.Sci.Soc.2013，36（2）：373-383.

The Maximum Value for the Harary Index of Unicyclic Graphs with a Given Girth

Chen Dandan
（Department of Public Course，Hunan Financial&Industrial Vocational-Technical College，Hengyang 421002，China）

In this paper，we first give a formula for calculating the Harary index of a unicyclic graph according to the structure，and then using this formula，we obtain the maximum value for the Harary index of unicyclic graphs with a given girth，and characterize the extremal graph with respect to the Harary index.

Girth Unicyclic graph Harary index Reciprocal distance

2016年05月09日