哈林圖的零階廣義Randic指標(biāo)的若干極值問題

劉順琴

（廈門大學(xué)嘉庚學(xué)院 信息與計算科學(xué)系，福建 漳州 363105）

哈林圖的零階廣義Randic指標(biāo)的若干極值問題

劉順琴

（廈門大學(xué)嘉庚學(xué)院 信息與計算科學(xué)系，福建 漳州 363105）

當(dāng)α＞0（α＜0）時，確定了n階哈林圖中具有最小（最大）零階廣義Randic指標(biāo)的圖類；當(dāng)α=-1及--時，給出了有t片樹葉的樹圖對應(yīng)的哈林圖中具有最大和最小零階廣義Randic指標(biāo)的圖類。

哈林圖；樹葉；最小；零階廣義Randic指標(biāo)

1 零階廣義Randic指標(biāo)

著名的化學(xué)家Randic在1975年研究分子結(jié)構(gòu)時引入了圖的一個重要的拓?fù)洳蛔兞喀郑渲笑侄x為圖G=（V，E）中所有頂點對的度數(shù)的乘積開方再求倒數(shù)之和，即

Randic同時指出該分支指標(biāo)與烷烴類物質(zhì)的很多物理性質(zhì)和化學(xué)性質(zhì)都顯示出了巨大的關(guān)聯(lián)性，如臨界溫度、生成焓、表面積以及水溶解度等等，稱χ為分支指標(biāo)后面，直接將該指標(biāo)成為圖的Randic指標(biāo)。

Randic已經(jīng)被多數(shù)的化學(xué)家們接受，該指標(biāo)能夠非常好地描述分子的結(jié)構(gòu)特性和結(jié)構(gòu)活性之間的關(guān)聯(lián)性，甚至是一個廣受化學(xué)家們喜愛的拓?fù)洳蛔兞浚珺.Bollobas聯(lián)合P.Erdos在1998年將Randic指標(biāo)中的推廣到任意一個非零實數(shù)α，提出了廣義的Randic指標(biāo)，即

L.B.Kier和L.H.Hall于1977年在文獻(xiàn)【1】當(dāng)中定義了零階Randic指標(biāo)如下：

后來，X.Li和J.Zheng在文獻(xiàn)【2】中提出了圖的零階廣義Randic指標(biāo)0Rα，就是將零階Randic指標(biāo)當(dāng)

2 哈林圖

定義：哈林圖是這樣得到的，對于沒有2度定點的n（n≥4）階樹的平面嵌入，將其樹葉按順序連成一個圈，這樣得到的平面圖稱之為哈林圖。

例如，如下的輪圖L（n）和星形圖S（n）：

可以看出，n階輪圖L（n）是通過n階星形圖S（n）（樹）得到的哈林圖。

從同構(gòu)的意義上看，其具有唯一性，但是這一點并不具備普遍性，例如：如下兩棵樹T1和T2，顯然T1同構(gòu)于T2，但它們所對應(yīng)的哈林圖H1并不同構(gòu)于H2。

為了討論方便，我們先定義如下幾個哈林圖的圖類：

設(shè)λ（n）是所有哈林圖的集合；

設(shè)Γ是如下n階的哈林圖的圖類；

當(dāng)n=2k時，Γ表示所有的三正則的哈林圖的集合；

當(dāng)n=2k+1時，Γ表示由一個頂點度數(shù)為4，其余頂點度數(shù)均為3的哈林圖的集合。

設(shè)Γ（t）表示具有t片樹葉的樹圖所對應(yīng)的哈林圖的集合，并且在該集合中定義下面兩個子圖類：

Γm（t）表示至少有t個頂點（對應(yīng)樹圖當(dāng)中的t片樹葉）的度數(shù)為3，其余頂點度數(shù)要么為要么為但最后度數(shù)總和要等于2n+2t-2的哈林圖的集合。

ΓM（t）表示由一個頂點的度數(shù)為2t+1-n，其余頂點度數(shù)為3的哈林圖的集合。

3 哈林圖零階廣義Randic指標(biāo)的極值問題

定理1：設(shè)H是λ（n）中的一個哈林圖，則有：

取等號當(dāng)且僅當(dāng)H是一個三正則圖，要求n為偶數(shù)，所以n=2k時，H是一個三正則的哈林圖；當(dāng)n=2k +1時，不存在n階三正則圖，自然沒有三正則的哈林圖，至少有一個頂點的度≥4，則0Rα（H）≥4α+（n-1）·3α，取等號當(dāng)且僅當(dāng)有一個頂點度數(shù)為4，其余頂點度數(shù)為3，即有0Rα（H）≥由Γ的定義，可知，等號成立當(dāng)且僅當(dāng)H∈Γ，

我們用D（H）=（d1，d2，…dn）表示哈林圖H的度序列，這里di表示第i個頂點的度，設(shè)di≥dj≥4，設(shè)哈林圖H′是用頂點對（di+1，dj-1）代替圖H的頂點對（di，dj）而得到的，

引理1：對于上面描述的H和H′，有

因此，引理1得證。

同樣用D（H）=（d1，d2，…dn）表示哈林圖H的度序列，若有di-dj≥2，哈林圖H″是用頂點對（di-1， dj+1）代替H中的頂點對而得到的。

根據(jù)引理1，我們有下面的推論：

推論：對于上面描述的H和H″，有

定理2：

對任意H∈Γ（t），H1∈Γm（t），H2∈ΓM（t），有

證明：由引理1，對于具有t片樹葉的樹圖，其對應(yīng)的哈林圖H的邊數(shù)是n-1+t且3度頂點的個數(shù)至少是t（即原來的樹圖中的t片樹葉所對應(yīng)的頂點數(shù)），為方便討論，在H中，我們還是把這t個頂點稱為‘樹葉'。

對任意H∈Γ（t），若H?ΓM（t），則有滿足di≥dj≥4的頂點對按照引理1，我們對度序列進(jìn)行調(diào)整，則將調(diào)整為（di+1，dj-1），調(diào)整之后的度序列所得到的哈林圖H′滿足0R-1（H′）＞0R-1（H），若H′的度序列（d1′，d2′，…dn′）中仍然有di′≥dj′≥4，則繼續(xù)調(diào)整為（di′+1，dj′-1），……，調(diào)整到不能再調(diào)整為止，這個時候得到的哈林圖H2的度序列（d1′′，d2′′，…dn′′）當(dāng)中，最多只有一個頂點v的度大于3，其余頂點的度均為3（否則可以繼續(xù)調(diào)整），按照握手定理，此時d（v）自然為（2n+2t-2-3（n-1））= 2t+1-n，按照ΓM（t）的定義，有H2∈ΓM（t）。

對任意H∈Γ（t），若H?Γm（t），即除了有t個‘樹葉'的度數(shù)為3之外，有其余頂點的度數(shù)滿足di-dj≥2，則將調(diào)整為（di-1，dj+1），則按照引理1的推論，我們知道，得到的哈林圖H″滿足0R-1（H″）＜0R-1（H），若仍然有H″?Γm（t），則繼續(xù)將度序列進(jìn)行調(diào)整，調(diào)整到不能再調(diào)整為止，得到的圖記為H1，則H1中除了t片樹葉的度數(shù)為3以外，其余頂點的度最多只差1，按照握手定理，則H1其余頂點的度數(shù)要么為?且總度數(shù)要等于2n+2t-2，按照Γm（t）的定義，有H1∈Γm（t）。

從證明過程可以看出，0R-1（H1）=0R-1（H）當(dāng)且僅當(dāng)H∈Γm（t），0R-1（H）=0R-1（H2）當(dāng)且僅當(dāng)H∈ΓM（t）。

定理證明完畢。

引理2：對于上面描述的H和H′，有

證明：

推論：對于上面描述的H和H″，有

證明：道理同引理1的推論，省略。

定理3：

其中0

證明：根據(jù)引理2及其推論，證明過程與定理2完全相同，省略。

［1］ L B Kier，L H Hall，The nature of structure-activity relationshiPs and their relation tomolecular connectivity［J］.EuroP.J.Med.Chem，1997（12）：307-312.

［2］ X Li，JZheng，A unified aPProach to the extremal trees for different indices［J］.Math ComPut Chem，2005（6）：137-142.

［3］ 陳錦松，郭曉峰.關(guān)于Randic指數(shù)及圖的直徑［J］.廈門大學(xué)學(xué)報（自然科學(xué)版），2009（4）：467-469.

［4］ 林啟法，錢建國.給定最大匹配數(shù)的樹的零階廣義Randic指標(biāo)［J］.純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué)，2010（2）：153-157.

［5］ 郝曉輝，李寶鳳.關(guān)于圖的似拉普拉斯譜半徑［J］.數(shù)學(xué)的實踐和認(rèn)識，2008（4）：158-160.

［6］ 葉圣奎，陳勝.圖的LaPlace譜半徑的幾類上界［J］數(shù)學(xué)學(xué)報，2008（2）：235-240.

［7］ 馮長君，陳艷，堵錫華.改進(jìn)的連接性指數(shù)用于鏈烷烴熱力學(xué)性質(zhì)與沸點研究［J］.吉林大學(xué)學(xué)報（自然科學(xué)版），2000（3）：80-84.

［8］ 張惠玲，曲安京.共軛單圈圖的廣義Randic指標(biāo)［J］.計算機與應(yīng)用化學(xué)，2013（6）：648-650.

［9］ 王波，冶成福.單圈圖σ指標(biāo)的次小值［J］.東北師范大學(xué)學(xué)報（自然科學(xué)版），2009（2）：18-24.

［10］ 陳婭紅.完美匹配單圈圖的維納指數(shù)［J］.上海交通大學(xué)學(xué)報，2010（6）：844-848.

［11］ 朱建明，許濤，何新英.二部圖上完美匹配的正交匹配分解［J］.運籌與管理，2008（4）：51-55.

［12］ 王世英，方坤夫.一些圖的完美匹配多面體的維數(shù)［J］.鄭州大學(xué)學(xué)報（自然科學(xué)版），2000（2）：1-3.

責(zé)任編輯：程艷艷

Some Extremum Problem s of Halin GraPhsWith Zero-order General Randic Index

LIU Shunqin
（DePartment of Information and ComPuter Science，Tan Kah Kee College of Xiamen University，Zhangzhou 363105，China）

We characterize the graPhs that have the smallest（largest）zero-order general Randic index in Halin graPhs with n-order whenα＞0（α＜0）；Also，we give the Halin graPhswith the smallest（largest）zero-order general Randic index corresPonding to the tree graPh with t Pieces of leaves whenα=-1 or-

Halin graPhs；tree graPh；the smallest；zero-order general Randic index

O157.5

A

1009-3907（2015）06-0053-04

2015-03-16

福建省科技廳自然科學(xué)基金項目（JB13269）

劉順琴（1981-），女，福建泉州人，講師，碩士，主要從事應(yīng)用數(shù)學(xué)方面研究。