两类一致膨胀图的PI指数*

红 霞,卫 哲

(洛阳师范学院 数学科学学院,河南 洛阳 471022)

1 引言

拓扑指数能反映有机分子的某些结构特征，并且对刻画分子图和建立分子结构与特征之间的关系具有重要作用. 目前已有很多关于图的顶点PI指数和边PI指数的研究[1-9].最近，李星星等人确定了特殊图的笛卡尔积图的PI指数[9].本文研究圈图和轮图的一致膨胀图,计算出了它们的PI指数.

2 基本概念

本文中的图均为简单无向图,相关术语可见文献[4].设G是连通图,用dG(u,v)表示G中从顶点u到顶点v的距离.对于边e∈E(G)，记NG(e)为e在G中的边邻域，NG[e]=NG(e)∪{e}为e在G中边闭邻域，dG(e)=|NG(e)|为e在G中的度.本文将dG(e)简记为d(e).对n≥1，记Pn为含有n个顶点的路，Fn+1为含有n+1个顶点的扇图，即一个顶点与Pn的各顶点都相连的图.对n≥3，记Cn为含有n个顶点的圈，Wn+1为含有n+1个顶点的轮图，即一个顶点与圈Cn上每个顶点相连而成的图.

定义1[8]对于图G，设V(G)={v1,v2,…,vn}，定义G的膨胀图FG为：G的一个顶点vi对应到FG的一个顶点集Vi，V(FG)={vij|vij∈Vi,i=1,2,…,n,j=1,2,…ti,|Vi|=ti∈Z+}，vijvkl∈E(FG)，j=1,2,…,ti，l=1,2,…,ti当且仅当i=k或vivk∈E(G).显然，当t1=t2=…=tn=1时FG=G.若t1=t2=…=tn，则称FG为G的一致膨胀图，记作UFG.

定义2[8]令图G=(V,E)是简单连通图,图G的PI指数定义为

这里边e=uv,neu(e|G)表示G中到点u的距离比到点v的距离更近的边的数目，nev(e|G)表示G中到点v的距离比到点u的距离更近的边的数目.G中与点u和点v距离相等的边不计入e的PI指数.将neu(e|G)简记为neu.

下文中将G中与点u和点v距离不相等的边的数目记为ne.

引理1[8]对于扇图Fn+1，有

引理2对于圈图Cn，有

证明设V(Cn)={v1,v2,…,vn},E(Cn)={ei=viv(i+1)(modn)|i=1,2,…,n}.对于e∈uv且i=1,2,…,n，当n为偶数时有nei=n-2，所以PI(Cn)=n(n-2)；当n为奇数时有nei=n-1，所以PI(Cn)=n(n-1).

引理3[2]对于轮图Wn+1，有

3 主要结果

定理1对于圈图Cn，有

证明对于e=uv且i=1,2,…,n，分以下两种情况讨论.

当n为偶数时，对于e∈[Vi,Vi],易知UFCn中不与e关联的边与点u和点v等距，即ne=d(e)=d(u)+d(v)-2.因此

对于e∈[Vi,V(i+1)(modn)]，在UFCn中与e相关联的边均与点u和点v不等距，故

d(e)=2(3t-2)=6t-4.

在UFCn中不与e关联且到点u和点v不等距的边的数目为

故

综上，有

当n为奇数时，对于e∈[Vi,Vi],与上述情况相同，有

对于e∈[Vi,V(i+1)(modn)]，在UFCn中与e相关联的边均与点u和点v不等距，故

d(e)=2(3t-2)=6t-4.

在UFCn中不与e关联且到点u和点v不等距的边的数目为

故

综上，有

定理2对于轮图Wn+1，有

证明设V(Wn+1)={v0,v1,…,vn}.注意到UFW3+1为完全图，此时易证结论成立.

设n=4，e∈uv且i=1,2,3,4.对于e∈[Vi,Vi],易知UFWn+1中不与e关联的边与点u和点v等距，即ne=d(e)=d(u)+d(v)-2.因此

对于e∈[V5,V5],易知UFWn+1中不与e关联的边与点u和点v等距，故ne=d(e)=2(5t-2)=10t-4.因此

对于e∈[Vi,V(i+1)(mod4)]，在UFW4+1中与e相关联的边均与点u和点v不等距，故

d(e)=2(4t-2)=8t-4.

在UFW4+1中不与e关联且到点u和点v不等距的边的数目为

故

对于e∈[Vi,V5]，在UFW4+1中与e相关联的边均与点u和点v不等距，故

d(e)=(4t-2)+(5t-2)=9t-4.

综上，有

设n≥5，e∈uv且i=1,2,…,n.对于e∈[Vi,Vi]，易知UFWn+1中不与e关联的边与点u和点v等距，故ne=d(e)=2(4t-2)=8t-4.因此

对于e∈[Vn+1,Vn+1]，易知UFWn+1中不与e关联的边与点u和点v等距，从而ne=d(e)=2(n+1)-4.因此

对于e∈[Vi,V(i+1)(modn)]，在UFWn+1中与e相关联的边均与点u和点v不等距，故

d(e)=2(4t-2)=8t-4.

在UFWn+1中不与e关联且到点u和点v不等距的边的数目为

故

对于e∈[Vi,Vn+1]，在UFWn+1中与e相关联的边均与点u和点v不等距，故

d(e)=(4t-2)+((n+1)t-2)=(n+5)t-4.

在UFWn+1中不与e关联且到点u和点v不等距的边的数目为

故

综上，有

4 总结

本文通过对一致膨胀图的边进行分类讨论，确定了圈图和轮图的一致膨胀图的PI指数.该方法还可用于研究更多图类的一致膨胀图，如完全图、完全多部图、正则图等.