桂云

(蚌埠學(xué)院數(shù)理系，安徽蚌埠 233000）

單圈圖的次小Randic指數(shù)

桂云

(蚌埠學(xué)院數(shù)理系，安徽蚌埠 233000）

單圈圖；次?。籖andic指數(shù)

廣義Randic指數(shù)定義為其中α為任意實(shí)數(shù)，d(x)表示頂點(diǎn)x的度，E(G)表示圖G的邊集.Randic指數(shù)可以看作廣義Randic指數(shù)在α＝－的特殊情形.用到的相關(guān)概念與符號(hào)如下：V(G)表示圖G的頂點(diǎn)集；表示圖G頂點(diǎn)個(gè)數(shù)；G中所有與頂點(diǎn)x相鄰接的頂點(diǎn)組成的集合記為N(x)；度為1的頂點(diǎn)稱為懸掛點(diǎn)；無(wú)圈的連通圖稱為樹(shù)；n個(gè)頂點(diǎn)的樹(shù)若有n－1個(gè)懸掛點(diǎn)，則稱為星，記為Sn；恰有一個(gè)圈的簡(jiǎn)單連通圖稱為單圈圖，表示從星Sn的兩個(gè)懸掛點(diǎn)添加一個(gè)邊所構(gòu)成的單圈圖.其他未定義的術(shù)語(yǔ)與符號(hào)參閱文獻(xiàn)［1］.Randic指數(shù)的研究目前已有了大量的成果，部分成果可以參閱文獻(xiàn)［2－5］.

1 引理與結(jié)論

證明若G是n個(gè)頂點(diǎn)的圈，則G為正則圖，由引理1知R(G)＝.故以下討論時(shí)均假定G不是n

nnnn個(gè)頂點(diǎn)的圈.

對(duì)n進(jìn)行數(shù)學(xué)歸納.

當(dāng)n＝5時(shí)可直接驗(yàn)證，5個(gè)頂點(diǎn)的單圈圖只有圖3所示4種：

圖1 結(jié)構(gòu)圖

圖2 結(jié)構(gòu)圖

圖35 個(gè)頂點(diǎn)單圈圖的結(jié)構(gòu)圖

易知R(U1)＝2.2071(最小)，R(U2)＝2.3045(次小)，R(U3)＝2.3938，R(U4)＝2.4319，結(jié)論成立.

現(xiàn)考慮n≥6的情形，記PV為Gn中的懸掛點(diǎn)集，因?yàn)镚n不是n個(gè)頂點(diǎn)的圈，故PV≠?.令u∈PV，v是u的相鄰點(diǎn)，則d(v)≥2，記，按如下方式選取u0：

1)u0的選取使W(u0)中的元素最多；

2)在滿足1)的條件下，d(v)最小.

圖4 G'＝時(shí)Gn結(jié)構(gòu)圖

當(dāng)n＝6，7，8時(shí)，不等式(1)右邊分別等于0.07055，0.120008，0.152544，均大于 0；當(dāng)n≥9，同情形1.1，可證g(n)+h(3)＞0，即n≥6時(shí)，R(Gn)＞f(n)，結(jié)論成立.

情形2存在某些i，1≤i≤d－1，使得d(yi)＝1.

不失一般性，假設(shè)d(y1)＝d(y2)＝…＝d(yk)＝1和d(yi)≥2，k+1≤i≤d－1，因?yàn)閗≥1，所以

情形2.1若d＝n－1，則Gn＝S+n與Gn的選擇矛盾.

情形2.2若d＝n－2，則Gn只有圖5所示3種圖.

圖5 d＝n－2時(shí)Gn結(jié)構(gòu)圖

R(U2)＞R(U1)，定理1前述部分已證，且易證R(U3)＞R(U1)，結(jié)論成立.

情形2.3若d≤n－3，

Gn為單圈圖，故k≤d－2.由式(1)與引理3得

d≤n－3，由式(2)與引理4又可得

此外，由情形2.2的討論可知，當(dāng)且僅當(dāng)Gn＝時(shí)，R(Gn)＝f(n)，證畢.

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

［1］徐俊明.圖論及其應(yīng)用［M］.2版.北京：中國(guó)科學(xué)技術(shù)大學(xué)出版社，2004

［2］LU M，LIU H，TIAN F.The Connectivity Index，MATCH Commun［J］.Math Comput Chem，2004(51)：149－154

［3］GAO J，LU M.On the Randic Index of Unicyclic Graphs［J］.MATCH Commun Math Comput Chem，2005(53)：377－384

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

［5］詹麗麗，劉素勤.給定懸掛點(diǎn)的三圈圖的零階廣義Randic指數(shù)［J］.重慶工商大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，29(6)：4－8

The Second Minimum Randic Index in Unicyclic Graphs

GUI Yun

(Department of Mathematics and Physics，Bengbu University，Bengbu 233000China)

Unicyclic graph；second minimum；Randic index

10.16055/j.issn.1672－058X.2015.0004.003

O157.5

A

1672－058X(2015)04－0012－04

2014－08－18；

2014－09－26.

桂云(1979－)，男，安徽蚌埠人，助教，碩士，從事圖論研究.