兩類一致膨脹圖的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指數.該方法還可用于研究更多圖類的一致膨脹圖，如完全圖、完全多部圖、正則圖等.