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

高　煒，梁　立

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

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

高煒，梁立

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在以下證明過(guò)程中，假設(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可得，，等號(hào)成立的充要條件是

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

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

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

通過(guò)計(jì)算，可知

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

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

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

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

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

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

證明：設(shè)Gmax是階為n的k-邊連通圖中使廣義哈拉里指數(shù)最大的圖，X是Gmax的邊割集，且滿足|V|=k，則Gmin?X有兩個(gè)分支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，則共有對(duì)頂點(diǎn)的距離為1，a1a2對(duì)頂點(diǎn)的距離為3，其他?a1a2對(duì)頂點(diǎn)的距離為2，因而有

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

2　結(jié)束語(yǔ)

我們通過(guò)假設(shè)和歸納找到了給定參數(shù)下圖的廣義哈拉里指數(shù)的極值，并得到了若干上下界結(jié)果，還說(shuō)明了在什么圖結(jié)構(gòu)下這些指數(shù)可以達(dá)到上下界。所得結(jié)果對(duì)于新材料和新藥物的研制具有一定的指導(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é)報(bào)（自然科學(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

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

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