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

呂寧寧，馬艷麗

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

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

呂寧寧，馬艷麗

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

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

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

1 引 言

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

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

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

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

2 引 理

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

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

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

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

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

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

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

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

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

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

3 主要結(jié)論

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

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

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

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

先看 （1）的證明：

1）若b＝2，則G就是由Sn－1對其中一邊插入一個2度點所得到的圖．

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

由1）、2）可知，b＝2，即此時的極值圖G為：在星圖Sn－1的一條邊上插入一個2度點．

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

因為a＋b＝n，則當(dāng)n為偶數(shù)時，

2

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

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

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

斷言1 G不含圈．

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

所以可知G不含圈．

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

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

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

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

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

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

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

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

斷言2 G中任意三圈不交于同一頂點．

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

所以G中任意三圈不交于同一頂點．

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

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

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

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

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

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

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

斷言2 G中任意三圈不交于同一頂點．

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

所以G中任意三圈不交于同一頂點．

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

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

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

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

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

斷言1 G不含圈．

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

則由引理3可知

所以可知G不含圈．

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

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

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

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

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

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

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

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

斷言2 所有圈交于同一頂點x．

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

所以G中所有圈交于同一頂點．

斷言3 度數(shù)為1的頂點必與最大度頂點關(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的頂點必與最大度頂點關(guān)聯(lián)．

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

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

斷言1 G不含圈．

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

所以可知G不含圈．

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

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

由斷言1和斷言2可知，當(dāng)α＞1時，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ù)的共軛樹 ［J］．甘肅聯(lián)合大學(xué)學(xué)報，2010．23（01）：17－20

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

［15］ 呂寧寧，王春生．雙圈仙人掌圖的零階廣義Randic指數(shù)的界 ［J］．河北北方學(xué)院學(xué)報：自然科學(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

來稿日期：2011 06 14

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

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

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