兩類(lèi)一致膨脹圖的PI指數(shù)*

紅 霞,衛(wèi) 哲

(洛陽(yáng)師范學(xué)院 數(shù)學(xué)科學(xué)學(xué)院,河南 洛陽(yáng) 471022)

1 引言

拓?fù)渲笖?shù)能反映有機(jī)分子的某些結(jié)構(gòu)特征，并且對(duì)刻畫(huà)分子圖和建立分子結(jié)構(gòu)與特征之間的關(guān)系具有重要作用. 目前已有很多關(guān)于圖的頂點(diǎn)PI指數(shù)和邊PI指數(shù)的研究[1-9].最近，李星星等人確定了特殊圖的笛卡爾積圖的PI指數(shù)[9].本文研究圈圖和輪圖的一致膨脹圖,計(jì)算出了它們的PI指數(shù).

2 基本概念

本文中的圖均為簡(jiǎn)單無(wú)向圖,相關(guān)術(shù)語(yǔ)可見(jiàn)文獻(xiàn)[4].設(shè)G是連通圖,用dG(u,v)表示G中從頂點(diǎn)u到頂點(diǎn)v的距離.對(duì)于邊e∈E(G)，記NG(e)為e在G中的邊鄰域，NG[e]=NG(e)∪{e}為e在G中邊閉鄰域，dG(e)=|NG(e)|為e在G中的度.本文將dG(e)簡(jiǎn)記為d(e).對(duì)n≥1，記Pn為含有n個(gè)頂點(diǎn)的路，F(xiàn)n+1為含有n+1個(gè)頂點(diǎn)的扇圖，即一個(gè)頂點(diǎn)與Pn的各頂點(diǎn)都相連的圖.對(duì)n≥3，記Cn為含有n個(gè)頂點(diǎn)的圈，Wn+1為含有n+1個(gè)頂點(diǎn)的輪圖，即一個(gè)頂點(diǎn)與圈Cn上每個(gè)頂點(diǎn)相連而成的圖.

定義1[8]對(duì)于圖G，設(shè)V(G)={v1,v2,…,vn}，定義G的膨脹圖FG為：G的一個(gè)頂點(diǎn)vi對(duì)應(yīng)到FG的一個(gè)頂點(diǎn)集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當(dāng)且僅當(dāng)i=k或vivk∈E(G).顯然，當(dāng)t1=t2=…=tn=1時(shí)FG=G.若t1=t2=…=tn，則稱(chēng)FG為G的一致膨脹圖，記作UFG.

定義2[8]令圖G=(V,E)是簡(jiǎn)單連通圖,圖G的PI指數(shù)定義為

這里邊e=uv,neu(e|G)表示G中到點(diǎn)u的距離比到點(diǎn)v的距離更近的邊的數(shù)目，nev(e|G)表示G中到點(diǎn)v的距離比到點(diǎn)u的距離更近的邊的數(shù)目.G中與點(diǎn)u和點(diǎn)v距離相等的邊不計(jì)入e的PI指數(shù).將neu(e|G)簡(jiǎn)記為neu.

下文中將G中與點(diǎn)u和點(diǎn)v距離不相等的邊的數(shù)目記為ne.

引理1[8]對(duì)于扇圖Fn+1，有

引理2對(duì)于圈圖Cn，有

證明設(shè)V(Cn)={v1,v2,…,vn},E(Cn)={ei=viv(i+1)(modn)|i=1,2,…,n}.對(duì)于e∈uv且i=1,2,…,n，當(dāng)n為偶數(shù)時(shí)有nei=n-2，所以PI(Cn)=n(n-2)；當(dāng)n為奇數(shù)時(shí)有nei=n-1，所以PI(Cn)=n(n-1).

引理3[2]對(duì)于輪圖Wn+1，有

3 主要結(jié)果

定理1對(duì)于圈圖Cn，有

證明對(duì)于e=uv且i=1,2,…,n，分以下兩種情況討論.

當(dāng)n為偶數(shù)時(shí)，對(duì)于e∈[Vi,Vi],易知UFCn中不與e關(guān)聯(lián)的邊與點(diǎn)u和點(diǎn)v等距，即ne=d(e)=d(u)+d(v)-2.因此

對(duì)于e∈[Vi,V(i+1)(modn)]，在UFCn中與e相關(guān)聯(lián)的邊均與點(diǎn)u和點(diǎn)v不等距，故

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

在UFCn中不與e關(guān)聯(lián)且到點(diǎn)u和點(diǎn)v不等距的邊的數(shù)目為

故

綜上，有

當(dāng)n為奇數(shù)時(shí)，對(duì)于e∈[Vi,Vi],與上述情況相同，有

對(duì)于e∈[Vi,V(i+1)(modn)]，在UFCn中與e相關(guān)聯(lián)的邊均與點(diǎn)u和點(diǎn)v不等距，故

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

在UFCn中不與e關(guān)聯(lián)且到點(diǎn)u和點(diǎn)v不等距的邊的數(shù)目為

故

綜上，有

定理2對(duì)于輪圖Wn+1，有

證明設(shè)V(Wn+1)={v0,v1,…,vn}.注意到UFW3+1為完全圖，此時(shí)易證結(jié)論成立.

設(shè)n=4，e∈uv且i=1,2,3,4.對(duì)于e∈[Vi,Vi],易知UFWn+1中不與e關(guān)聯(lián)的邊與點(diǎn)u和點(diǎn)v等距，即ne=d(e)=d(u)+d(v)-2.因此

對(duì)于e∈[V5,V5],易知UFWn+1中不與e關(guān)聯(lián)的邊與點(diǎn)u和點(diǎn)v等距，故ne=d(e)=2(5t-2)=10t-4.因此

對(duì)于e∈[Vi,V(i+1)(mod4)]，在UFW4+1中與e相關(guān)聯(lián)的邊均與點(diǎn)u和點(diǎn)v不等距，故

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

在UFW4+1中不與e關(guān)聯(lián)且到點(diǎn)u和點(diǎn)v不等距的邊的數(shù)目為

故

對(duì)于e∈[Vi,V5]，在UFW4+1中與e相關(guān)聯(lián)的邊均與點(diǎn)u和點(diǎn)v不等距，故

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

綜上，有

設(shè)n≥5，e∈uv且i=1,2,…,n.對(duì)于e∈[Vi,Vi]，易知UFWn+1中不與e關(guān)聯(lián)的邊與點(diǎn)u和點(diǎn)v等距，故ne=d(e)=2(4t-2)=8t-4.因此

對(duì)于e∈[Vn+1,Vn+1]，易知UFWn+1中不與e關(guān)聯(lián)的邊與點(diǎn)u和點(diǎn)v等距，從而ne=d(e)=2(n+1)-4.因此

對(duì)于e∈[Vi,V(i+1)(modn)]，在UFWn+1中與e相關(guān)聯(lián)的邊均與點(diǎn)u和點(diǎn)v不等距，故

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

在UFWn+1中不與e關(guān)聯(lián)且到點(diǎn)u和點(diǎn)v不等距的邊的數(shù)目為

故

對(duì)于e∈[Vi,Vn+1]，在UFWn+1中與e相關(guān)聯(lián)的邊均與點(diǎn)u和點(diǎn)v不等距，故

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

在UFWn+1中不與e關(guān)聯(lián)且到點(diǎn)u和點(diǎn)v不等距的邊的數(shù)目為

故

綜上，有

4 總結(jié)

本文通過(guò)對(duì)一致膨脹圖的邊進(jìn)行分類(lèi)討論，確定了圈圖和輪圖的一致膨脹圖的PI指數(shù).該方法還可用于研究更多圖類(lèi)的一致膨脹圖，如完全圖、完全多部圖、正則圖等.