陳單單

（湖南財(cái)經(jīng)工業(yè)職業(yè)技術(shù)學(xué)院公共課部，湖南，衡陽，421002）

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

陳單單

（湖南財(cái)經(jīng)工業(yè)職業(yè)技術(shù)學(xué)院公共課部，湖南，衡陽，421002）

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

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

1　引言

拓?fù)渲笖?shù)是從化合物的結(jié)構(gòu)圖衍生出來的一種數(shù)學(xué)不變量.大約在一百多年之前就引入了拓?fù)渲笖?shù)，至今已有200多種被證實(shí)在結(jié)構(gòu)-活性/性質(zhì)相關(guān)性（QSAR/QSPR）中非常有用，這些指數(shù)中有些是基于圖中點(diǎn)的距離，有些是基于圖中點(diǎn)的度數(shù).而Harary指數(shù)是基于圖中點(diǎn)的距離.

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

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

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

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

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

若G=（V，E）是一個(gè)n階單圈圖，其中的圈Cm=v1v2…vmv1的長度為m （即圍長）且m≤n ，則G-E（Cm）的連通分支Ti（i=1，2，…，m）都是樹，Ti與Cm的公共頂點(diǎn)為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為其中一個(gè)端點(diǎn)的li+1階路，則G= U （Cm；T1，T2，…，Tm）=U （Cm；Pl1+1，Pl2+1，…，Plm+1）.

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

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

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

引理2 設(shè)Cn是n階單圈圖，則

下面我們給出關(guān)于單圈圖Harary指數(shù)的一個(gè)計(jì)算方法.

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

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

（i）設(shè)兩個(gè)頂點(diǎn)都在圈Cm上的反距離之和為H1，則

（ii）設(shè)兩個(gè)頂點(diǎn)中一個(gè)在圈Cm上，另一個(gè)在某Ti-｛vi｝上的反距離之和為H2，則

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

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

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

因此，

從而

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

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

定理4 設(shè)G=U（Cm；T1，T2，…，Tm）是一個(gè)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））.

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

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

因?yàn)?/p>

而

因此，對于x ∈Cm，有

和

同樣地，有

由定理3得

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

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

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

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

等號成立當(dāng)且僅當(dāng)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）等號成立當(dāng)且僅當(dāng)l2=0，即

利用定理3，我們可計(jì)算出兩個(gè)圍長分別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日