高　煒，梁　立

（云南師范大學(xué)信息學(xué)院，昆明650500）

給定參數(shù)下圖的廣義哈拉里指數(shù)

高煒，梁立

（云南師范大學(xué)信息學(xué)院，昆明650500）

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

理論化學(xué)；廣義哈拉里指數(shù)；上下界

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

大量的實(shí)驗(yàn)結(jié)果表明，新材料和新藥物的部分特性（如熔點(diǎn)、沸點(diǎn)和毒性）和它們的分子結(jié)構(gòu)有密切的關(guān)聯(lián)?；诖耍芯咳藛T在分子結(jié)構(gòu)圖上定義了一些化學(xué)指數(shù)，并試圖通過化學(xué)指數(shù)的計(jì)算進(jìn)一步研究這些新材料和新藥物的化學(xué)性質(zhì)。這種通過計(jì)算就能確定某種化學(xué)物質(zhì)特性的方法，避免了化學(xué)實(shí)驗(yàn)所需要的高投入。

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

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

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

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

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

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

1　主要結(jié)論及證明

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

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

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

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

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

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

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

注意到Tk, n的團(tuán)數(shù)是k，因此有

下面利用對頂點(diǎn)數(shù)n的歸納，證明廣義哈拉里指數(shù)的下界。

設(shè)G*是有n個頂點(diǎn)、團(tuán)數(shù)k

通過計(jì)算，可知

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

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

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

設(shè)G1和G2的頂點(diǎn)數(shù)分別為n1和n2，則有n1+ n2+k=n，且

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

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

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

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

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

2　結(jié)束語

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

［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］許冬冬，高煒.超維納指數(shù)的若干結(jié)果［J］.云南師范大學(xué)學(xué)報（自然科學(xué)版），2014（5）：46-50.

［8］高云，高煒.修改的維納指數(shù)和修改的超維納指數(shù)的若干結(jié)果［J］.生物物理學(xué)，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.

【責(zé)任編輯王云鵬】

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

國家自然科學(xué)青年基金資助項(xiàng)目（11401519）

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