扇及其一致膨脹圖的PI指數*

何麗麗， 黃 敏， 郝建修

(浙江師范大學數理與信息工程學院，浙江金華 321004)

0 引言

Wiener(W)指數和Szeged(Sz)指數均用于反映有機分子的某些結構特征．PI指數是一個類似于Wiener指數的拓撲指數，PI指數在實際生產和生活中有著非常廣泛的應用．例如，文獻［1］介紹了PI指數用于描述有機分子的毒性(QSTR)和活性(QSAR);文獻［2-3］討論了通過計算一些納米結構的PI指數以深入探究其特性等．

本文主要研究簡單連通圖的PI指數．一個圖G的PI指數定義為

其中：對于邊e=uv，neu(e|G)表示G中到點u的距離比到點v的距離更近的邊的數目;nev(e|G)是指G中到點v的距離比到點u的距離更近的邊的數目;求和符號表示取遍G中所有邊．G中與點u和點v距離相等的邊不計入e的PI指數．將neu(e|G)簡記為neu．

1 預備知識

本文相關的一些基本定義詳見文獻［4-5］．

定義1［5］圖 G 為扇當且僅當 V(G)={vi|i=0，1，2，…，n}，E(G)={v0vi|i=1，2，…，n}∪{vivi+1|i=1，2，…，n-1}，此時圖 G 可記為 Fn．且易得，|E(Fn)|=2n-1．

定義2［5］對一個圖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=t，則稱FG為G的一致膨脹圖，記作UFG．

定義3［2］設圖G是一個連通的簡單圖，對任意的邊e=uv∈E(G)，定義ne為G中與點u和點v距離不相等的邊的數目．

定義4［4］設A，B 為圖G 中的點集，定義［A，B］為G 中點集A與點集B 間的邊，|［A，B］|表示A與B間的邊數．

定義5 設邊e=uv∈E(G)，定義d(e)=d(uv)=d(u)+d(v)-2，其中d(u)和d(v)分別為點u和點v在圖G中的度．

2 主要結果

定理1 對n≥3，有 PI(Fn)=2n2+2n-8．

證明 容易驗證，PI(F3)=16，PI(F4)=32．因此，當n=3，n=4時，定理1成立．

下證當n≥5時定理1也成立．將 Fn的邊分別記為 e2i-1=v0vi，e2i=vivi+1，i=1，2，…，n，如圖1所示．

圖1 Fn扇

由定義3可得

故當n為奇數時，

當n為偶數時，

定理1得證．

其中，t如定義2所定義．

證明 由于UFF1和UFF2為完全圖，因此容易驗證此時定理2成立．

下面將圖UFFn的邊分2種情形討論．

1)e∈［Vi，Vi］(i=0，1，2，…，n)．設 e=uv，易見，UFFn中不與 e關聯的邊與點 u 和點 v等距．故此時ne等于 d(e)，亦即 ne=d(u)+d(v)-2．因此

對于邊 v0jv1l∈UFFn，［V0，Vi］中關聯于 v0j的邊和［V1，V2］中關聯于 v1l的邊均與點 v0j和點 v1l不等距，其中 i=1，2，…，n．然而，Fn中其他對 e=v0v1的 PI指數有貢獻的邊此時膨脹為［Vi，Vk］(i，k=3，4，…，n，i≠k)中的 t2條邊，且［V0，V0］和［V0，V1］中各存在 t-1 條邊關聯于 v0j，［V1，V1］和［V1，V0］中也各存在t-1條邊關聯于v1l．V3，V4，…，Vn中的邊均與點v0j和點v1l不等距．因此，由定義3可以驗證

由PI指數的定義可得

因此，綜合1)和2)可得

當n=3和n=4時，可用同樣的方法證得定理2．定理2證畢．

［1］Khadikar P V，Karmarkar S，Agrawal V K．A novel PI index and its applications to QSPR/QSAR studies［J］．J Chem Inf Comput Sci，2001，41(4)：934-949．

［2］Hao Jianxiu．The PI index of gated amalgam［J］．Ars Combinatoria，2009，91：135-145．

［3］Hao Jianxiu．PI index of some simple pericondensed hexagonal systems［J］．Ars Combinatoria，2009，92：137-147．

［4］Bondy J A，Murty U S R．Graph theory with applications［M］．London：Macmillan Press Ltd，1976．

［5］許振宇，穆勇．扇與Halin圖的一致膨脹圖的關聯色數［J］．濟南大學學報：自然科學版，2006，20(3)：264-266．