齒輪圖及其一致膨脹圖的PI指數

弓文慧 邵燕靈

文章編號? 1000-5269（2024）01-0027-04

DOI：10.15958/j.cnki.gdxbzrb.2024.01.03

收稿日期：2022-12-04

基金項目：國家自然科學基金資助項目（61774137）；山西省回國留學人員科研項目（2022-149）；山西省自然科學基金資助項目（20210302124212）

作者簡介：弓文慧（1996—），女，在讀碩士，研究方向：圖論和組合數學，E-mail：g13623458238@163.com.

*通訊作者：邵燕靈，E-mail：ylshao@nuc.edu.cn.

摘? 要：齒輪圖就是在輪圖的輪圈上每相鄰兩點之間均添加一個頂點后得到的圖，由于齒輪圖有很好的對稱性，所以將其邊進行分類，計算出齒輪圖的PI指數。齒輪圖的一致膨脹圖就是將它的每個頂點都替換成階相等的完全圖，通過與齒輪圖類比，計算其一致膨脹圖的PI指數，為研究一些特殊圖形的PI指數問題提供了線索。

關鍵詞：PI指數;齒輪圖;一致膨脹圖;圖對稱性;類比

中圖分類號：O157.5

文獻標志碼：A

Padamkar-Ivan指數是2000年Padamkar V Khadikar提出的一個新的拓撲指數，并將其縮寫為PI指數。PI指數對刻畫分子圖以及建立分子結構與特征之間的關系具有重要作用，同時被廣泛應用于預測化合物的物理、化學性質及生物活性。文獻［1-4］陸續得到了雙圈圖和三圈圖的PI極值，文獻［5-8］分別得到了苯類烴分子圖、環形六面體、乘積圖、橋圖和鏈圖等特殊圖類的PI指數。本文選擇了齒輪圖和齒輪圖的一致膨脹圖這兩類特殊圖進行研究，計算它們的PI指數。

1? 相關定義

定義1［9-10］? 設G為簡單連通圖，V（G）表示其頂點集，E（G）表示其邊集。e∈E（G）是連接V（G）中點u和點v的一條邊，記作e=uv。一條邊到一個頂點的距離就是該點與該邊的兩個端點之間的最小距離。設e=uv，用neu（e|G）表示G中到點u的距離比到點v的距離更近的邊的數目，nev（e|G）表示G中到點v的距離比到點u的距離更近的邊的數目。

一個圖G的PI指數定義為

PI（G）=∑e=uv∈E（G）[neu（e|G）+nev（e|G）]

定義2［11］? 設n為一個正整數，一個n-圈Cn定義為一個包含n個頂點和n條邊的圖，且滿足下列性質：將邊記為e1，e2，…，en，頂點記為a1，a2，…，an，對每個j，ej的端點是aj－1和aj，其中：1≤j≤n，a0=an。

定義3［11］? 由一個n-圈Cn添加一個新的頂點v0，并將頂點v0與Cn的所有n個頂點相連，得到的圖稱為輪圖，記為Wn。此時，稱圈Cn為輪圖Wn的輪圈，點v0為輪心。

定義4［12］? 齒輪圖是在輪圖Wn的輪圈Cn的每條邊上都添加一個頂點后所得的圖，記為G2n+1。記齒輪圖的輪心為v0，Cn上的頂點依次記為v1，v2，…，vn，在邊v1v2，v2v3，…，vn－1vn，vnv1上添加的點依次記為u1，u2，…，un－1，un。齒輪圖G2n+1如圖1所示。

定義5［13］? 對一個圖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∈Ζ+}，vijvkl∈E（FG），其中，j=1，2，…，ti，l=1，2，…，tk，當且僅當i=k或vivk∈E（G）。顯然，當t1=t2=…=tn=1時，FG=G。若t1=t2=…=tn=t，則稱FG為G的一致膨脹圖，記作UFG。

定義6［14］? 設圖G是一個連通的簡單圖，對任意的邊e=uv∈E（G），定義ne為G中與點u和點v距離不相等的邊數。

定義7［15］? 設A，B為圖G中兩個不相交的頂點子集，定義[A，B]為G中點集A到點集B間的邊，[A，B]表示A與B間的邊數；特別地，定義[A，A]為G中由點集A導出的子圖中的所有邊，[A，A]表示G中由A導出的子圖的邊數。

2? 主要結果

定理1? 設n≥2，G2n+1為如圖1所示的齒輪圖，則PI（G2n+1）=3n（3n－3）。

證明? 設齒輪圖G2n+1的頂點集V（G2n+1）={vi，uj|i=0，1，2，…，n;j=1，2，…，n}，邊集E（G2n+1）={v0vi，viuj|i=1，2，…，n;j=1，2，…，n}，其中i=j或者i=j+1（mod n），容易驗證其頂點數為2n+1，邊數為3n。記E1（G2n+1）={v0vi|i=1，2，…，n}，E2（G2n+1）=E（G2n+1）/E1（G2n+1）并設PIi=∑e∈Ei（G2n+1） [nev（e|G2n+1）+neu（e|G2n+1）]，其中i=1，2。

先設e=v0v1∈E1（G2n+1），從圖1中可以發現邊vnun，v2u1到點v0和v1的距離相等，因此nev0（e|G2n+1）+nev1（e|G2n+1）=3n－3。易知E1（G2n+1）=n，由圖的對稱性可得PI1=n（3n－3）。

再設e=v1un∈E2（G2n+1），從圖1中可以發現邊v0vn，vn－1un－1到點v1和un的距離相等，因此nev1（e|G2n+1）+neun（e|G2n+1）=3n－3。易知E2（G2n+1）=2n，由圖的對稱性可得PI2=2n（3n－3）。

綜上所述， PI（G2n+1）=PI1+PI2=3n（3n－3）。定理1得證。

定理2? 設n≥2，UFG2n+1為齒輪圖G2n+1（如圖1所示）的一致膨脹圖，則

PI（UFG2n+1）=

9t4 + 50t3-35t2 + 10t，? n=2；

63t4 + 82t3-87t2 + 14t，? n=3；

4n3-72n2-92nt4-n3-152n2-272n-1t3-

（4n2 + 16n + 3）t2 + （4n + 2）t，n≥4。

證明? 如圖1，V（G2n+1）={v0，v1，v2，…，vn，u1，u2，…，un}，頂點vi分別對應UFG2n+1中的頂點集Vi（i=0，1，2，…，n），頂點ui分別對應頂點集Ui（i=1，2，…，n）。對n≥2，在圖UFG2n+1中可以得到[Vi，Vi]=t（t－1）2，i=0，1，2，…，n;[Ui，Ui]=t（t－1）2，[Vi，V0]=t2，[Vi，Uk]=t2，其中i，k=1，2，…，n。類比圖G2n+1可以發現圖UFG2n+1也存在對稱性，故在以下的證明過程中，可將圖UFG2n+1的邊分為5類。

1）對n=2，UFG2n+1中與頂點集V0相鄰的頂點集只有V1和V2。以下分別討論：

（1）e∈[Vi，Vi]（i=1，2），設e=vijvil（j，l=1，2，…，t，且j≠l）。易證，在UFG2n+1中與e關聯的邊到點vij和點vil的距離均不相等，則ne=d（e）。故有

ne=d（vij）+d（vil）－2

=（4t－1）+（4t－1）－2=8t－4，

∑e∈[Vi，Vi]ne=（8t－4）·t（t－1）2=4t3－6t2+2t。

（2）e∈[Ui，Ui]（i=1，2），設e=uijuil（j，l=1， 2，…，t，且j≠l）。易證，在UFG2n+1中與e關聯的邊到點uij和點uil的距離均不相等。則有

ne=d（uij）+d（uil）－2

=（3t－1）+（3t－1）－2=6t－4，

∑e∈[Ui，Ui]ne=（6t－4）·t（t－1）2=3t3－5t2+2t。

（3）e∈[V0，V0]，設e=v0jv0l（j，l=1，2，…，t，且j≠l）。易證，在UFG2n+1中與e關聯的邊到點v0j和點v0l的距離均不相等。則有

ne=d（v0j）+d（v0l）－2

=（3t－1）+（3t－1）－2=6t－4，

∑e∈[V0，V0]ne=（6t－4）·t（t－1）2=3t3－5t2+2t。

（4）e∈[Vi，Uk]（i，k=1，2），設e=vijukl（j，l=1，2，…，t，且j≠l）。易證，在UFG2n+1中與e關聯的邊到點vij和點ukl的距離均不相等，因此

ne=d（vij）+d（ukl）－2

=（4t－1）+（3t－1）－2=7t－4；

在UFG2n+1中不與e關聯且到點vij和點ukl的距離不相等的邊數ne=3·t（t－1）2，故

∑e∈[Vi，Uk]ne=7t－4+3t（t－1）2t2

=32t4+112t3－4t2。

（5）e∈[Vi，V0]（i=1，2），設e=vijv0l（j，l=1，2，…，t，且j≠l）。易證，在UFG2n+1中與e關聯的邊到點vij和點v0l的距離均不相等，因此

ne=d（vij）+d（v0l）－2

=（4t－1）+（3t－1）－2=7t－4；

在UFG2n+1中不與e關聯且到點vij和點v0l的距離不相等的邊數ne=3·t（t－1）2，故

∑e∈[Vi，V0]ne=7t－4+3t（t－1）2t2

=32t4+112t3－4t2。

綜上所述，

PI（UFG2n+1）=∑2i=1（∑e∈[Vi，Vi]ne+∑e∈[Ui，Ui]ne+∑e∈[Vi，V0]ne）+

∑2i=1∑2k=1∑e∈[Vi，Uk]ne+∑e∈[V0，V0]ne

=2（4t3－6t2+2t+3t3－5t2+2t+32t4+

112t3－4t2）+4（32t4+112t3－4t2）+（3t3－5t2+2t）

=9t4+50t3－35t2+10t。

2）對n=3，情形（1）、情形（2）與上述相同，以下討論情形（3）、（4）、（5）。

（1）e∈[V0，V0]，設e=v0jv0l（j，l=1，2，…，t，且j≠l）。易證，在UFG2n+1中與e關聯的邊到點v0j和點v0l的距離不相等。則有

ne=d（v0j）+d（v0l）－2

=（4t－1）+（4t－1）－2=8t－4，

∑e∈[V0，V0]ne=（8t－4）·t（t－1）2

=4t3－6t2+2t。

（2）e∈[Vi，Uk]（i，k=1，2，3），設e=vijukl（j，l=1，2，…，t，且j≠l）。易證，在UFG2n+1中與e關聯的邊到點vij和點ukl的距離均不相等，因此

ne=d（vij）+d（ukl）－2

=（4t－1）+（3t－1）－2=7t－4；

在UFG2n+1中不與e關聯且到點vij和點ukl的距離不相等的邊數ne=5·t（t－1）2+3t2，故

∑e∈[Vi，Uk]ne=7t－4+5·t（t－1）2+3t2t2

=112t4+92t3－4t2。

（3）e∈[Vi，V0]（i=1，2，3），設e=vijv0l（j，l=1，2，…，t，且j≠l）。易證，在UFG2n+1中與e關聯的邊到點vij和點v0l的距離均不相等，因此

ne=d（vij）+d（v0l）－2

=（4t－1）+（4t－1）－2=8t－4；

在UFG2n+1中不與e關聯且到點vij和點v0l的距離不相等的邊數ne=5·t（t－1）2+2t2，故

∑e∈[Vi，V0]ne=8t－4+5·t（t－1）2+2t2t2

=92t4+112t3－4t2。

綜上所述，

PI（UFG2n+1）=∑3i=1（∑e∈[Vi，Vi]ne+∑e∈[Ui，Ui]ne+

∑e∈[Vi，V0]ne）+∑3i=1∑3k=1∑e∈[Vi，Uk]ne+∑e∈[V0，V0]ne

=3（4t3－6t2+2t+3t3－5t2+2t+92t4+112t3－

4t2）+9（112t4+92t3－4t2）+（4t3－6t2+2t）

=63t4+82t3－87t2+14t。

3）下設n≥4，以下只討論后3種情形。

（1）e∈[V0，V0]，設e=v0jv0l（j，l=1，2，…，t，且j≠l）。在UFG2n+1中與e關聯的邊到點v0j和點v0l的距離均不相等。則有

ne=d（v0j）+d（v0l）－2

=[（n+1）t－1]+[（n+1）t－1]

=2（n+1）t－4，

∑e∈[V0，V0]ne=[2（n+1）t－4]·t（t－1）2

=（n+1）t3－（n+3）t2+2t。

（2）e∈[Vi，Uk]（i，k=1，2，…，n），設e=vijukl （j，l=1，2，…，t，且j≠l）。易證，在UFG2n+1中與e關聯的邊到點vij和點ukl的距離均不相等，因此

ne=d（vij）+d（ukl）－2

=（4t－1）+（3t－1）－2=7t－4；

在UFG2n+1中不與e關聯且到點vij和點ukl的距離不相等的邊數ne=（2n－1）·t（t－1）2+（3n－6）t2，故

∑e∈[Vi，Uk]ne=7t－4+（2n－1）·t（t－1）2+（3n－6）t2t2

=4n－132t4+152－nt3－4t2。

（3）e∈[Vi，V0]（i，k=1，2，…，n），設e=vijv0l （j，l=1，2，…，t，且j≠l）。易證，在UFG2n+1中與e關聯的邊到點vij和點v0l的距離均不相等，因此

ne=d（vij）+d（v0l）－2

=（4t－1）+[（n+1）t－1]－2

=（n+5）t－4；

在UFG2n+1中不與e關聯且到點vij和點v0l的距離不相等的邊數ne=（2n－1）·t（t－1）2+（2n－4）t2，故

∑e∈[Vi，V0]ne=（n+5）－4+（2n－1）·t（t－1）2+

（2n－4）t2t2

=3n－92t4+112t3－4t2。

綜上所述，

PI（UFG2n+1）=∑ni=1（∑e∈[Vi，Vi]ne+∑e∈[Ui，Ui]ne+∑e∈[Vi，V0]ne）+

∑ni=1∑nk=1∑e∈[Vi，Uk]ne+∑e∈[V0，V0]ne

=n4t3－6t2+2t+3t3－5t2+2t+3n－92t4 +

112t3－4t2+n24n－132t4+152－nt3－4t2+

（n+1）t3－（n+3）t2+2t

=4n3－72n2－92nt4－n3－152n2－272n－1t3－

（4n2+16n+3）t2+（4n+2）t。

定理2得證。

3? 結論

本文利用圖的對稱性，將復雜圖的邊分類來討論各自的PI值。通過將齒輪圖的一致膨脹圖與原圖進行類比，把結構較為簡單的原圖中計算PI指數的方法運用到結構較為復雜的一致膨脹圖中，得到了齒輪圖及其一致膨脹圖的PI指數公式。

參考文獻：

[1]MA G， WANG J F. Disproving a conjecture on PI-index of graphs［J］. MATCH Communications in Mathematical and in Computer Chemistry， 2022， 88： 199-203.

［2］ VUKICEVIC Z K， STEVANOVIC D. Bicyclic graphs with extremal values of PI index［J］. Discrete Applied Mathematics， 2013， 161： 395-403.

［3］ MA G， BIAN Q J， JI S J， et al. Tricyclic graphs with minimum values of PI index［J］. Match-Communications in Mathematical and in Computer Chemistry， 2016， 76： 43-60.

［4］ MA G， BIAN Q J， JI S J， et al. Tricyclic graphs with maximum PI index［J］. Ars Combinatoria， 2021， 155： 157-168.

［5］ JOHN P E， KHADIKAR P V. A method of computing the PI index of benzenoid hydrocarbons using orthogonal cuts［J］. Journal of Mathematical Chemistry， 2007， 42： 37-45.

［6］ LIU S， ZHANG H. PI index of toroidal polyhexes［J］. Match-Communications in Mathematical and in Computer Chemistry， 2010， 63： 217-238.

［7］ YOUSEFI-AZARI H， MANOOCHEHRIAN B， ASHRAFI A R. The PI index of product graphs［J］. Applied Mathematics Letters， 2008， 21： 624-627.

［8］ MANSOUR T， SCHORK M. The PI index of bridge and chain graphs［J］. Match-Communications in Mathematical and in Computer Chemistry， 2009， 62： 723-734.

［9］ KHADIKAR P V . On a novel structural descriptor PI［J］. National Academy Science Letters-India， 2000， 23： 113-118.

［10］KHADIKAR P V， KARMARKAR S. A novel PI index and its applications to QSPR/QSAR studies［J］. Journal of Chemical Information and Modeling， 2001， 41： 934-949.

［11］BOLLOBAS B. Modern graph theory［M］. New York： Springer-Verlag， 1998.

［12］BRANDSTADT A， LE V B， SPINRAD J P. Graph classes：a survey［M］. Society for Industrial and Applied Mathematics， 1999.

［13］KOSTOCHKA A K， WOODALL D R. Choosability conjectures and multicircuits［J］. Discrete Mathematics， 2001， 240： 123-143.

［14］HAO J X. The PI index of gated amalgam［J］. Ars Combinatoria， 2009， 91： 135-145.

［15］BONOY J A， MURTY U S R. Graph theory with applications［M］. London： Macmillan Press Ltd， 1976．

（責任編輯：曾? 晶）

PI Index of Gear Graph and Uniform Inflation Graph

GONG Wenhui， SHAO Yanling*

（ School of Mathematics， North University of China， Taiyuan 030051， China）

Abstract：

Gear graph is obtained by adding a vertex between each adjacent two vertexs on the cyclic of the wheel graph. Because the gear graph has strictly symmetry， it is used to classify its edges and calculate the PI index of gear graph.The uniform inflation graph of gear graph is to replace each vertex with a complete graph of equal order. By analogy with gear graph， the PI index of the uniform inflation graph is calculated， which provides a clue for the study of the PI index of some special graphs.

Key words：

PI index; gear graph; uniform inflation graph; symmetry; analogously