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

呂寧寧，馬艷麗

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

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

呂寧寧，馬艷麗

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

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

仙人掌圖；零階廣義Randic指數；界

1 引 言

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

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

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

首先介紹一些定義．Δ（G），δ（G）分別表示圖的頂點最大度和最小度；ni表示度數為i的頂點個數；Cn、Pn分別表示有n個頂點的圈和路；度數為1的頂點稱為懸掛點．L（n，r）表示有r個懸掛點的n階連通仙人掌圖的集合．G（n，r）表示：當n－r－1為偶數時，在星圖Sn上添加 （n－r－1）／2條獨立邊，當（n－r－1）為奇數時，在星圖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）表示：當n－r－1為偶數時，（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條懸掛邊；當n－r－1為奇數時，（n－r－4）／2個C3與一個C4相連接，并且每兩個圈至多有一個公共點，則這樣得到的圖有4度點，有個2度點，當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是正實數，且滿足a－2≥b≥1，則有

（1）當α∈ （－∞，0）∪ （1，＋∞）時，aα＋bα＞ （a－1）α＋（b＋1）α

（2）當α∈ （0，1）時，aα＋bα＜ （a－1）α＋（b＋1）α

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

（1）當α∈ （－∞，0）∪ （1，＋∞）時，aα＋bα＜ （a＋1）α＋（b＋1）α

（2）當α∈ （0，1）時，aα＋bα＞ （a＋1）α＋（b－1）α

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

（1）當α＞0時，y＞0

（2）當α＜0時，y＜0

3 主要結論

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

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

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

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

先看 （1）的證明：

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

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

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

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

因為a＋b＝n，則當n為偶數時，

2

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

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

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

斷言1 G不含圈．

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

所以可知G不含圈．

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

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

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

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

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

斷言1 G含圈的個數越多越好．

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

所以G含圈，而且含圈的個數越多越好．

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

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

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

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

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

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

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

斷言1 G含圈的個數越多越好．

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

所以G含圈，而且含圈的個數越多越好．

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

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

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

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

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

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

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

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

斷言1 G不含圈．

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

則由引理3可知

所以可知G不含圈．

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

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

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

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

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

斷言1 G含圈的個數越多越好．

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

所以G含圈，而且含圈的個數越多越好．

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

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

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

斷言3 度數為1的頂點必與最大度頂點關聯．

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

所以可知G的度數為1的頂點必與最大度頂點關聯．

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

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

斷言1 G不含圈．

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

所以可知G不含圈．

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

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

由斷言1和斷言2可知，當α＞1時，R0α取得極小值當且僅當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指數的共軛樹 ［J］．甘肅聯合大學學報，2010．23（01）：17－20

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

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

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

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

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