单圈图的次小Randic指数

桂云

(蚌埠学院数理系，安徽蚌埠 233000）

单圈图的次小Randic指数

桂云

(蚌埠学院数理系，安徽蚌埠 233000）

单圈图；次小；Randic指数

广义Randic指数定义为其中α为任意实数，d(x)表示顶点x的度，E(G)表示图G的边集.Randic指数可以看作广义Randic指数在α＝－的特殊情形.用到的相关概念与符号如下：V(G)表示图G的顶点集；表示图G顶点个数；G中所有与顶点x相邻接的顶点组成的集合记为N(x)；度为1的顶点称为悬挂点；无圈的连通图称为树；n个顶点的树若有n－1个悬挂点，则称为星，记为Sn；恰有一个圈的简单连通图称为单圈图，表示从星Sn的两个悬挂点添加一个边所构成的单圈图.其他未定义的术语与符号参阅文献［1］.Randic指数的研究目前已有了大量的成果，部分成果可以参阅文献［2－5］.

1 引理与结论

证明若G是n个顶点的圈，则G为正则图，由引理1知R(G)＝.故以下讨论时均假定G不是n

nnnn个顶点的圈.

对n进行数学归纳.

当n＝5时可直接验证，5个顶点的单圈图只有图3所示4种：

图1 结构图

图2 结构图

图35 个顶点单圈图的结构图

易知R(U1)＝2.2071(最小)，R(U2)＝2.3045(次小)，R(U3)＝2.3938，R(U4)＝2.4319，结论成立.

现考虑n≥6的情形，记PV为Gn中的悬挂点集，因为Gn不是n个顶点的圈，故PV≠∅.令u∈PV，v是u的相邻点，则d(v)≥2，记，按如下方式选取u0：

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

2)在满足1)的条件下，d(v)最小.

图4 G'＝时Gn结构图

当n＝6，7，8时，不等式(1)右边分别等于0.07055，0.120008，0.152544，均大于 0；当n≥9，同情形1.1，可证g(n)+h(3)＞0，即n≥6时，R(Gn)＞f(n)，结论成立.

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

不失一般性，假设d(y1)＝d(y2)＝…＝d(yk)＝1和d(yi)≥2，k+1≤i≤d－1，因为k≥1，所以

情形2.1若d＝n－1，则Gn＝S+n与Gn的选择矛盾.

情形2.2若d＝n－2，则Gn只有图5所示3种图.

图5 d＝n－2时Gn结构图

R(U2)＞R(U1)，定理1前述部分已证，且易证R(U3)＞R(U1)，结论成立.

情形2.3若d≤n－3，

Gn为单圈图，故k≤d－2.由式(1)与引理3得

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

此外，由情形2.2的讨论可知，当且仅当Gn＝时，R(Gn)＝f(n)，证毕.

2 结束语

［1］徐俊明.图论及其应用［M］.2版.北京：中国科学技术大学出版社，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指标［J］.计算机与应用化学，2013，30(6)：648－650

［5］詹丽丽，刘素勤.给定悬挂点的三圈图的零阶广义Randic指数［J］.重庆工商大学学报：自然科学版，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－)，男，安徽蚌埠人，助教，硕士，从事图论研究.