呂寧寧，馬艷麗

（安徽新華學(xué)院公共課教學(xué)部，安徽 合肥230088）

有r個(gè)懸掛點(diǎn)仙人掌圖的零階廣義Randic指數(shù)的界

呂寧寧，馬艷麗

（安徽新華學(xué)院公共課教學(xué)部，安徽 合肥230088）

設(shè)G為一簡(jiǎn)單連通圖，則G的零階廣義Randic指數(shù)定義為R0α（G）＝∑ν∈V（G）dα（ν），其中d（v）為頂點(diǎn)ν的度數(shù)，α為非0和1的實(shí)數(shù)．圖G稱之為仙人掌圖，如果G的每一塊要么是一條邊，要么是一個(gè)圈．本文研究有r個(gè)懸掛點(diǎn)仙人掌圖的零階廣義 Randic指數(shù)的界．L（n，r）、G（n，r）、H（n，r）、M（n，r）、N（n，r）分別表示一類圖．當(dāng)α＜0時(shí)，R0αG）取得極大值當(dāng)且僅當(dāng)G∈M（n，r），R0α取得極小值當(dāng)且僅當(dāng)G∈N（n，r）；當(dāng)0＜α＜1時(shí)，R0α取得極大值當(dāng)且僅當(dāng)G∈N（n，r），R0α取得極小值當(dāng)且僅當(dāng)G∈M（n，r）；當(dāng)α＞1時(shí)，R0α取得極大值當(dāng)且僅當(dāng)G∈G（n，r），R0α取得極小值當(dāng)且僅當(dāng)G∈H（n，r）．

仙人掌圖；零階廣義Randic指數(shù)；界

1 引 言

給定一個(gè)簡(jiǎn)單連通圖G＝（V（G），E（G）），其中V（G），E（G）分別表示圖G的頂點(diǎn)集合和邊集合．圖G的Randic指數(shù)定義為：，其中d（u）表示頂點(diǎn)u的度數(shù)［1］．

1998年Bollobas與Erdos［2］將 Randic指數(shù)進(jìn)行了推廣，得到廣義 Randic指數(shù)，即Rα（G）＝其中α為任意實(shí)數(shù)．零階 Randic指數(shù)是由 Kier與 Hall［3］提出，定義為R0（G）＝階廣義Randic指數(shù)［4］定義為：其中α為任意實(shí)數(shù)．零階廣義Randic指數(shù)的相關(guān)研究結(jié)果已有許多［5－7］．

圖G稱之為仙人掌圖，如果G的每一塊要么是一條邊，要么是一個(gè)圈．含兩個(gè)圈的仙人掌圖稱為雙圈仙人掌圖．M．Lu［8］給出了給定圈數(shù)的Randic指數(shù)下界，A．Lin［9］給出了有r個(gè)懸掛點(diǎn)仙人掌圖的Randic指數(shù)下界，其它相關(guān)研究結(jié)果見(jiàn)文獻(xiàn) ［10－15］．本文探討有r個(gè)懸掛點(diǎn)仙人掌圖的零階廣義Randic指數(shù)的界．

首先介紹一些定義．Δ（G），δ（G）分別表示圖的頂點(diǎn)最大度和最小度；ni表示度數(shù)為i的頂點(diǎn)個(gè)數(shù)；Cn、Pn分別表示有n個(gè)頂點(diǎn)的圈和路；度數(shù)為1的頂點(diǎn)稱為懸掛點(diǎn)．L（n，r）表示有r個(gè)懸掛點(diǎn)的n階連通仙人掌圖的集合．G（n，r）表示：當(dāng)n－r－1為偶數(shù)時(shí)，在星圖Sn上添加 （n－r－1）／2條獨(dú)立邊，當(dāng)（n－r－1）為奇數(shù)時(shí)，在星圖Sn－1上添加 （n－r－1）／2條獨(dú)立邊，并在其中一條獨(dú)立邊或懸掛邊上插入一個(gè)2度頂點(diǎn)．H（n，r）表示：一條長(zhǎng)為n－r＋1的路Pn－r＋1，在其中k0個(gè)2度點(diǎn)上添加k＋1條懸掛邊，在其余的n－r－k0個(gè)2度點(diǎn)上添加k條懸掛邊，其中r－2＝（n－r）k＋k0（k≥0，k0≥0，k0＜n－r）．M（n，r）表示在星圖Sr＋1的邊上插入n－r－1個(gè)2度點(diǎn)．N（n，r）表示：當(dāng)n－r－1為偶數(shù)時(shí)，（n－r－1）／2個(gè)C3相連接，并且每?jī)蓚€(gè)圈至多有一個(gè)公共點(diǎn)，則這樣得到的圖有度點(diǎn)，若r≤n－r＋3，令在其中k個(gè)2度點(diǎn)上添0加k＋1條懸掛邊，在其余的2度點(diǎn)上添加k條懸掛邊，若r＞n－r＋3，則在每個(gè)2度點(diǎn)上添加兩條懸掛邊，令r－（n－r＋3）＝2r－n－3＝（n－r）k＋k0，然后在其中的k0個(gè)4度點(diǎn)上添加k＋1條懸掛邊，在其余的n－r－k0個(gè)4度點(diǎn)上添加k條懸掛邊；當(dāng)n－r－1為奇數(shù)時(shí)，（n－r－4）／2個(gè)C3與一個(gè)C4相連接，并且每?jī)蓚€(gè)圈至多有一個(gè)公共點(diǎn)，則這樣得到的圖有4度點(diǎn)，有個(gè)2度點(diǎn)，當(dāng)r≤n－r＋4時(shí)，令k0個(gè)2度點(diǎn)上添加k＋1條懸掛邊，在其余的個(gè)2度點(diǎn)上添加k條懸掛邊，若r＞n－r＋4，則在每個(gè)2度點(diǎn)上添加兩條懸掛邊，令r－（n－r＋4）＝2r－n－4＝（n－r）k＋k0，然后在其中的k0個(gè)4度點(diǎn)上添加k＋1條懸掛邊，在其余的n－r－k0個(gè)4度點(diǎn)上添加k條懸掛邊．

2 引 理

為了以后的定理證明，首先給出幾個(gè)引理．

引理1［10］若a，b是正實(shí)數(shù)，且滿足a－2≥b≥1，則有

（1）當(dāng)α∈ （－∞，0）∪ （1，＋∞）時(shí)，aα＋bα＞ （a－1）α＋（b＋1）α

（2）當(dāng)α∈ （0，1）時(shí)，aα＋bα＜ （a－1）α＋（b＋1）α

引理2［10］若a，b是正實(shí)數(shù)，且滿足a≥b≥2，則有

（1）當(dāng)α∈ （－∞，0）∪ （1，＋∞）時(shí)，aα＋bα＜ （a＋1）α＋（b＋1）α

（2）當(dāng)α∈ （0，1）時(shí)，aα＋bα＞ （a＋1）α＋（b－1）α

引理3 當(dāng)x＞0時(shí)，對(duì)于y＝（x＋1）α－xα，有

（1）當(dāng)α＞0時(shí)，y＞0

（2）當(dāng)α＜0時(shí)，y＜0

3 主要結(jié)論

當(dāng)r＝n－1時(shí)，此時(shí)圖為星圖Sn，所以只考慮r≤n－2．

定理1 設(shè)圖G∈L（n，r），即G是有r個(gè)懸掛點(diǎn)的n階仙人掌圖，若r＝n－2，則

等號(hào)成立當(dāng)且僅當(dāng)G為：在星圖Sn－1的一條邊上插入一個(gè)2度點(diǎn)．

證明 因?yàn)镚有n－2個(gè)懸掛點(diǎn)，那么G正好有2個(gè)頂點(diǎn)度數(shù)≥2．設(shè)這兩個(gè)頂點(diǎn)為x，y，則可知G為樹(shù)．因?yàn)镚連通，懸掛點(diǎn)個(gè)數(shù)為n－2，我們可以得到n≥4，x與y相鄰，且對(duì)于任意一個(gè)懸掛點(diǎn)z要么與x相鄰，要么與y相鄰．設(shè)a，b分別為頂點(diǎn)x，y的度數(shù)，則a＋b＝n，不妨設(shè)a≥b．

先看 （1）的證明：

1）若b＝2，則G就是由Sn－1對(duì)其中一邊插入一個(gè)2度點(diǎn)所得到的圖．

2）若b≥3，則頂點(diǎn)y至少有2個(gè)懸掛點(diǎn)，設(shè)其中一個(gè)懸掛點(diǎn)為z，則可以構(gòu)造一個(gè)新的圖G′＝G－yz＋xz，顯然G′∈L（n，r），則由引理2可知

由1）、2）可知，b＝2，即此時(shí)的極值圖G為：在星圖Sn－1的一條邊上插入一個(gè)2度點(diǎn)．

再看 （2）的證明：只證明n為偶數(shù)的情形，n為奇數(shù)時(shí)類似可證．

因?yàn)閍＋b＝n，則當(dāng)n為偶數(shù)時(shí)，

2

2）若a＞b，則有a－2≥b≥2，此時(shí)我們假設(shè)x的一個(gè)懸掛點(diǎn)為z，則我們可以構(gòu)造一個(gè)新的圖G′＝G－xz＋yz，顯然G′∈L（n，r），則由引理1可知

定理2 設(shè)圖G∈L（n，r），即G是有r個(gè)懸掛點(diǎn)的n階仙人掌圖，若r≤n－3，則

證明 （1）1）設(shè)G為α＜0時(shí)零階廣義Randic指數(shù)取得最大的圖，則有如下斷言：

斷言1 G不含圈．

假設(shè)G含圈Cm∶x1x2…xmx1，則若去掉其中任意一邊，不妨設(shè)去掉邊x1xm后得到圖G′＝G－x1xm，顯然G′∈L（n，r）．則由引理3可知

所以可知G不含圈．

斷言2 G的頂點(diǎn)度數(shù)要么為1，要么為2，要么為Δ（G）．

假設(shè)還有其他度數(shù)，不妨設(shè)G中頂點(diǎn)x有最大度Δ（G），頂點(diǎn)y度數(shù)滿足條件Δ（G）≥y≥3，則可知頂點(diǎn)y至少有一鄰點(diǎn)z滿足任意一條zx路經(jīng)過(guò)頂點(diǎn)y，構(gòu)造圖G′＝G－yz＋xz，顯然G′∈L（n，r），則由引理2可知

所以可知G的頂點(diǎn)度數(shù)要么為1，要么為2，要么為Δ（G）．

由斷言1和斷言2可知，當(dāng)α＜0時(shí)，R0α取得極大值當(dāng)且僅當(dāng)G∈M（n，r）．

2）設(shè)G為α＜0時(shí)零階廣義Randic指數(shù)取得最小的圖，則有如下斷言：

斷言1 G含圈的個(gè)數(shù)越多越好．

假設(shè)G不含圈，則可以加一邊xy后得到一個(gè)新的圖G′＝G＋xy，顯然G′∈L（n，r）．則由引理3可知

所以G含圈，而且含圈的個(gè)數(shù)越多越好．

斷言2 G中任意三圈不交于同一頂點(diǎn)．

假設(shè)有三個(gè)圈C1、C2、C3交于同一頂點(diǎn)x，不妨設(shè)y為圈C2上且異于x的頂點(diǎn)，設(shè)頂點(diǎn)w、z與頂點(diǎn)x關(guān)聯(lián)且為圈C1上的點(diǎn)．構(gòu)造新圖G′＝G－wx－zx＋wy＋zy，顯然G′∈L（n，r）．此時(shí)dx－4≥dy≥2，則由引理1可知

所以G中任意三圈不交于同一頂點(diǎn)．

斷言3 G中頂點(diǎn)度數(shù)要么為1，要么為2，要么為3，要么為4（此時(shí)度數(shù)為4的頂點(diǎn)無(wú)懸掛邊）；或者要么為1，要么為Δ（G），要么為Δ（G）－1．

這也就是說(shuō)盡量將懸掛邊平均分到頂點(diǎn)上，且使得頂點(diǎn)度數(shù)盡量接近．

假如不按照這種方法分配懸掛邊，則會(huì)得到一圖G，G中有兩頂點(diǎn)x、y滿足dx－2≥dy≥2且x至少有一懸掛邊xz．可以得到一新圖G′＝G－zx＋zy，顯然G′∈L（n，r）．則由引理1可知

（2）1）設(shè)G為0＜α＜1時(shí)零階廣義Randic指數(shù)取得最大的圖，則有如下斷言：

斷言1 G含圈的個(gè)數(shù)越多越好．

假設(shè)G不含圈，則可以加一邊xy后得到一個(gè)新的圖G′＝G＋xy，顯然G′∈L（n，r）．則由引理3可知

所以G含圈，而且含圈的個(gè)數(shù)越多越好．

斷言2 G中任意三圈不交于同一頂點(diǎn)．

假設(shè)有三個(gè)圈C1、C2、C3交于同一頂點(diǎn)x，不妨設(shè)y為圈C2上且異于x的頂點(diǎn)，設(shè)頂點(diǎn)w、z與頂點(diǎn)x關(guān)聯(lián)且為圈C1上的點(diǎn)．我們構(gòu)造新圖G′＝G－wx－zx＋wy＋zy，顯然G′∈L（n，r）．此時(shí)dx－4≥dy≥2，則由引理1可知

所以G中任意三圈不交于同一頂點(diǎn)．

斷言3 G中頂點(diǎn)度數(shù)要么為1，要么為2，要么為3，要么為4（此時(shí)度數(shù)為4的頂點(diǎn)無(wú)懸掛邊）；或者要么為1，要么為Δ（G），要么為Δ（G）－1．

這也就是說(shuō)盡量將懸掛邊平均分到頂點(diǎn)上，且使得頂點(diǎn)度數(shù)盡量接近．

假如不按照這種方法分配懸掛邊，則會(huì)得到一圖G，G中有兩頂點(diǎn)x、y滿足dx－2≥dy≥2且x至少有一懸掛邊xz．可以得到一新圖G′＝G－zx＋zy，顯然G′∈L（n，r）．則由引理1可知

由斷言1、斷言2和斷言3可知，當(dāng)α＜0時(shí)，R0α取得極小值當(dāng)且僅當(dāng)G∈N（n，r）．

2）設(shè)G為0＜α＜1時(shí)零階廣義Randic指數(shù)取得最小的圖，則有如下斷言：

斷言1 G不含圈．

假設(shè)G含圈Cm∶x1x2…xmx1，則若去掉其中任意一邊，不妨設(shè)去掉邊x1xm后得到圖G′＝G－x1xm，顯然G′∈L（n，r）．

則由引理3可知

所以可知G不含圈．

斷言2 G的頂點(diǎn)度數(shù)要么為1，要么為2，要么為Δ（G）．

假設(shè)還有其他度數(shù)，不妨設(shè)G中頂點(diǎn)有x最大度Δ（G），頂點(diǎn)y度數(shù)滿足條件Δ（G）≥y≥3，則可知頂點(diǎn)y至少有一鄰點(diǎn)z滿足任意一條zx－路經(jīng)過(guò)頂點(diǎn)y，構(gòu)造圖G′＝G－yz＋xz，顯然G′∈L（n，r），則由引理2可知

所以可知G的頂點(diǎn)度數(shù)要么為1，要么為2，要么為Δ（G）．

由斷言1和斷言2可知，當(dāng)0＜α＜1時(shí)，R0α取得極大值當(dāng)且僅當(dāng)G∈M（n，r）．

（3）1）設(shè)G為α＞1時(shí)零階廣義Randic指數(shù)取得最大的圖，則有如下斷言：

斷言1 G含圈的個(gè)數(shù)越多越好．

假設(shè)G不含圈，則可以加一邊xy后得到一個(gè)新的圖G′＝G＋xy，顯然G′∈L（n，r）．則由引理3可知

所以G含圈，而且含圈的個(gè)數(shù)越多越好．

斷言2 所有圈交于同一頂點(diǎn)x．

假設(shè)存在一圈C，x?V（C），則必存在路P∶x…y，使得V（P）∩V（C）＝｛y｝．設(shè)頂點(diǎn)w、z與頂點(diǎn)y關(guān)聯(lián)且為圈C上的點(diǎn)．構(gòu)造新圖G′＝G＝wy－zy＋wx＋zx，顯然G′∈L（n，r）．則由引理2可知

所以G中所有圈交于同一頂點(diǎn)．

斷言3 度數(shù)為1的頂點(diǎn)必與最大度頂點(diǎn)關(guān)聯(lián)．

假設(shè)x，y∈V（G），d（y）＝1，d（x）＝Δ（G）．x與y不相鄰，則存在路P∶x…zy．構(gòu)造新圖G′＝G－zy＋xy，顯然G′∈L（n，r），則由引理2可知

所以可知G的度數(shù)為1的頂點(diǎn)必與最大度頂點(diǎn)關(guān)聯(lián)．

由斷言1、斷言2和斷言3可知，當(dāng)α＞1時(shí)，R0α取得極大值當(dāng)且僅當(dāng)G∈G（n，r）．

2）設(shè)G為α＞1時(shí)零階廣義Randic指數(shù)取得最小的圖，則有如下斷言：

斷言1 G不含圈．

假設(shè)G含圈Gm∶x1x2…xmx1，則若去掉其中任意一邊，不妨設(shè)去掉邊x1xm后得到圖G′＝G－x1xm，顯然G′∈L（n，r）．則由引理3可知

所以可知G不含圈．

斷言2 G中除1度點(diǎn)外，頂點(diǎn)度數(shù)要么為Δ（G），要么為Δ（G）－1．

假設(shè)圖G中有兩頂點(diǎn)x，y度數(shù)滿足dx－2≥dy≥2，則可知頂點(diǎn)x至少有一鄰點(diǎn)z滿足任意一條zy－路經(jīng)過(guò)頂點(diǎn)x，我們構(gòu)造圖G′＝G－xz－yz，顯然G′∈L（n，r），則由引理1可知

由斷言1和斷言2可知，當(dāng)α＞1時(shí)，R0α取得極小值當(dāng)且僅當(dāng)G∈H（n，r）．

［1］ Randic M．On the characterization of molecular branching ［J］．J Am Chem Soc，1975 （97）：6609－6615

［2］ Bollobas B，Erdos P．Graphs of extremal weights ［J］．Ars Combin，1998 （50）：225－233

［3］ Kier LB，Hall LH．Molecular connectivity in structure－analysis ［M］．Wiley，Chichester Research Studies Press，1986

［4］ Pavlovic LJ．Maximal value of the zeroth－order Randic index ［J］．Discrete Appl Math，2003 （127）：615－626

［5］ Hua H，Deng H．On unicycle graphs with maximum and minimum zeroth－order general Randic index ［J］．J Math Chem，2007 （41）：173－181

［6］ Li X，Zhao H．Trees with the first three smallest and largest generalized topological indices［J］．Match Commun Math Chem，2004 （50）：57－62

［7］ Wang H，Deng H．Unicycle graphs with maximum generalized topological indices［J］．J Math Chem，2007（42）：119－124

［8］ Lu M，Zhang L，Tian F．On the Randic index of cacti［J］．Match Commun Math Chem，2006 （56）：551－556

［9］ Lin A，Luo R．A sharp lower bound of the Randic index of cacti with r pendants［J］．Discrete Appl Math Lett，2008（156）：1725－1735

［10］ Lin A，Luo R．On sharp bounds of the zero－order Randic index of certain unicyclic graphs ［J］．Appl Math Lett，2009（22）：585－589

［11］ Bondy JA，Murty USR．Graph Theory［M］．Berlin：Springer，2008

［12］ Randic M．On structural ordering and branching of acyclic saturated hydrocarbons ［J］．J Math Chem，1998 （24）：345－358

［13］ 孫志榮，蔣珍珍．具有極小Hosoya指數(shù)的共軛樹(shù) ［J］．甘肅聯(lián)合大學(xué)學(xué)報(bào)，2010．23（01）：17－20

［14］ 劉家保，呂寧寧，潘向峰．一類單圈圖的優(yōu)美性和平衡性 ［J］．合肥學(xué)院學(xué)報(bào)，2008，18（02）：18－22

［15］ 呂寧寧，王春生．雙圈仙人掌圖的零階廣義Randic指數(shù)的界 ［J］．河北北方學(xué)院學(xué)報(bào)：自然科學(xué)版，2010，26（03）：10－12

On Bounds of Zero－order General Randic Index of Cacti with r Pendents

LV Ning－ning，MA Yan－li
（Department of Basic Coureses，Xinhua University，Hefei 230088，Anhui，China）

The zero－order general Randic index of a simple connected graph Gis defined as R0α（G）＝∑ν∈V（G）dα（ν），where d（ν）denotes the degree ofν，αis a given real number other than 0and 1．A graph G is called a cactus if each block of Gis either an edge or a cycle．In this paper，we present the sharp bounds of the zero－order general Randic index of cacti with r pendents．L（n，r），G（n，r），H（n，r），M（n，r）andN（n，r）denote some class of cacti respectvely．Whenα＜0，the maximal graph is in M（n，r）and the minimal graph is in N（n，r）；when 0＜α＜1，the maximal graph is in N（n，r）and the minimal graph is in M（n，r）；whenα＞1，the maximal graph is in G（n，r）and the minimal graph is in H（n，r）．

Cactus；Zero－order general Randic index；bound

O 157．5

A

1673－1492 （2011）05－0001－05

來(lái)稿日期：2011 06 14

國(guó)家自然科學(xué)基金項(xiàng)目 （10901001）；安徽新華學(xué)院資助科研項(xiàng)目（2011zr006）；安徽新華學(xué)院資助科研項(xiàng)目（2011zr007）

呂寧寧（1985－），女，安徽界首市人，安徽新華學(xué)院教師，碩士．

劉守義 英文編輯：劉彥哲］