給定參數下圖的廣義哈拉里指數

高　煒，梁　立

（云南師范大學信息學院，昆明650500）

給定參數下圖的廣義哈拉里指數

高煒，梁立

（云南師范大學信息學院，昆明650500）

在給定一些圖參數的條件下，得出了廣義哈拉里指數的上下界。

理論化學；廣義哈拉里指數；上下界

隨著化學實驗條件的改善和生物化學新技術的出現，越來越多的新材料和新藥物孕育而生。它們的物理、化學或生物特征都需要通過其化學結構進行分析，這大大增加了研究人員的工作量。如何精確、有效和快捷地分析這些新材料和新藥物的特性已成為研究人員的重要課題。

大量的實驗結果表明，新材料和新藥物的部分特性（如熔點、沸點和毒性）和它們的分子結構有密切的關聯。基于此，研究人員在分子結構圖上定義了一些化學指數，并試圖通過化學指數的計算進一步研究這些新材料和新藥物的化學性質。這種通過計算就能確定某種化學物質特性的方法，避免了化學實驗所需要的高投入。

在理論化學中，研究人員用圖結構描述分子結構，即用頂點表示原子，用邊表示原子之間的化學健。通常情況下，設G=(V( G), E( G))是一個圖，其中頂點集合V( G)表示原子集合，邊集合E( G)表示化學鍵集合。相關的化學指數研究結果可參考文獻［1-8］。若沒有特別說明，文中使用的標記、符號和定義與文獻［9］一致。

一個圖的哈拉里指數（Harary index）定義為

上述哈拉里指數H( G)也稱為第一哈拉里指數，而對應的第二和第三哈拉里指數定義如下：

Das等［10］給出的廣義哈拉里指數為

其中m是非負整數。m=0時，Hm(G)表示第一哈拉里指數；而m=1時，Hm(G)表示第二哈拉里指數；m=2時，Hm(G)表示第三哈拉里指數。

在本文中，我們通過固定一些圖參數，研究了此條件下廣義哈拉里指數的極值問題，并得到了哈拉里指數的上下界及上下界所對應的圖。

1　主要結論及證明

設Tk, n是一個有n個頂點的完全k-部圖，每個部分有個頂點。設χ(G)和c( G)分別是圖G的正常色數和團數（最大團的頂點數）。

證明：設在所有的n個頂點、k個正常色數的圖中，G*為廣義哈拉里指數最大的圖，則G*的頂點集可分成k個部分，且沒有連接屬于同一部分的兩個頂點的邊，但G*中屬于不同部分的兩個頂點都有邊相連。否則，若存在兩個不相連的頂點v和v′屬于不同的部分，則圖G?+vv′同樣滿足色數k，但卻擁有更大的廣義哈拉里指數，這與G*的取法矛盾。因此，G*是一個完全k-部圖Kk(r1, r2,…,rk)，其中r1+r2+…+rk=n，ri( i=1,2,…,k )表示第i個部分的頂點。

引理1［9］：設G是階為n的圖。若G包含Km+1，則有|E( G)|≤|E( Tk, n)|，等號成立的充要條件是

若c( G)=n或c( G)=n?1，則很容易找到廣義哈拉里數的上下界。

在以下證明過程中，假設G是階為n的圖，且滿足c( G)

定理2：設G是階為n的圖，且滿足c( G)=k< n?1，則有

證明：設G是階為n的圖，且滿足c( G)=k< n?1，l是圖G的直徑，則由引理1可得，，等號成立的充要條件是

注意到Tk, n的團數是k，因此有

下面利用對頂點數n的歸納，證明廣義哈拉里指數的下界。

設G*是有n個頂點、團數k

通過計算，可知

定理3：設G是階為n的k-連通圖，其中1≤k≤n?2，則有

證明：設Gmax是階為n的k-連通圖中使廣義哈拉里指數最大的圖。由于Gmax的連通度為k，因而存在一個頂點割集X?V( Gmax)滿足|X|=k。

設G1、G2、…、Gω為Gmax-X的分支，則每個子圖G1、G2、…、Gω都是完全圖，且ω=2。若ω>2，則增加一條從一個分支的某個頂點到另外一個分支某個頂點的邊，得到的圖連通度依然是k，但它的廣義哈拉里指數增加了，這與Gmax的取法矛盾。因此，Gmax-X只有兩個分支G1和G2，且G1和G2中任意的頂點都和X中的每一個頂點相連。

設G1和G2的頂點數分別為n1和n2，則有n1+ n2+k=n，且

對于固定的n和k，可知n1=1或n2=1時，上述值達到最大。此時Gmax=Kk∨(K1∪Kn? k?1)。通過計算，可知

定理4：設G是階為n的k-邊連通圖，其中1≤k≤n?2，則有

證明：設Gmax是階為n的k-邊連通圖中使廣義哈拉里指數最大的圖，X是Gmax的邊割集，且滿足|V|=k，則Gmin?X有兩個分支G1和G2，且G1和G2都是完全圖。設|V( G1)|=n1，|V( G2)|=n2，則有n1+n2=n。

設X在G1、G2上的終端頂點集合分別為S、T，且|V( G1)?S|=a1，|V( G2)?T|=a2，則共有對頂點的距離為1，a1a2對頂點的距離為3，其他?a1a2對頂點的距離為2，因而有

對于固定的n、k和m，上式在n1=1，a1=0或 n2=1，a2=0時達到最大，并且有，因而，有

2　結束語

我們通過假設和歸納找到了給定參數下圖的廣義哈拉里指數的極值，并得到了若干上下界結果，還說明了在什么圖結構下這些指數可以達到上下界。所得結果對于新材料和新藥物的研制具有一定的指導意義。

［1］FARAHANI M R，GAO W，KANNA M R R.On the Omega Polynomials of a Family of Hydrocarbon Molecules “Polycyclic Aromatic Hydrocarbons Pank”［J］.Asian A-cademic Research Journal of Multidisciplinary，2015，2 （7）:263-268.

［2］GAO W，SHI L.Wiener Index of Gear Fan Graph and Gear Wheel Graph［J］.Asian Journal of Chemistry，2014，26（11）:3397-3400.

［3］FARAHANI M R，GAO W.On Multiplicative and Redefined Version of Zagreb Indices of V-Phenylenic Nanotubes and Nanotorus［J］.British Journal of Mathematics &Computer Science，2016，13（5）:1-8.

［4］FARAHANI M R，GAO W.The Schultz Index and Schultz Polynomial of the Jahangir Graphs［J］.Applied Mathematics，2015，6:2319-2325.

［5］XI W F，GAO W.Geometric-arithmetic Index and Zagreb Indices of Certain Special Molecular Graphs［J］.Journal of Advances in Chemistry，2014，10（2）:2254-2261.

［6］GAO W，SHI L.Szeged Related Indices of Unilateral Polyomino Chain and Unilateral Hexagonal Chain［J］. IAENG International Journal of Applied Mathematics，2015，45（2）:138-150.

［7］許冬冬，高煒.超維納指數的若干結果［J］.云南師范大學學報（自然科學版），2014（5）：46-50.

［8］高云，高煒.修改的維納指數和修改的超維納指數的若干結果［J］.生物物理學，2015（3）：59-66.

［9］BONDY J A，MURTY U S R.Graph Theory with Applications［M］.London:Macmillan Press，1976:1-40.

［10］DAS A C，XU K X，CANGUL I N，et al.On the Harary Index of Graph Operations［J/OL］.Journal of Inequalities and Applications，2013，2013:339.［2015-12-26］.http:// www.journalofinequalitiesandapplications.com/content/2013/ 1/339.DOI:10.1186/1029-242X-2013-339.

【責任編輯王云鵬】

Generalized Harary Index of Graphs with Fixed Parameters

GAO Wei，LIANG Li
（School of Information，Yunnan Normal University，Kunming 650500，China）

Several upper and lower bounds of generalized Harary index were determined under the condition that some graph parameters were fixed.

theoretical chemistry；generalized Harary index；upper and lower bound

O157.6

A

2095-7726（2016）03-0001-03

2016-01-27

國家自然科學青年基金資助項目（11401519）

高煒（1981-），男，浙江紹興人，副教授，博士，研究方向：理論化學、機器學習和圖論。