弓文慧 邵燕靈

文章編號(hào)? 1000-5269（2024）01-0027-04

DOI：10.15958/j.cnki.gdxbzrb.2024.01.03

收稿日期：2022-12-04

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

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

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

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

關(guān)鍵詞：PI指數(shù);齒輪圖;一致膨脹圖;圖對(duì)稱性;類比

中圖分類號(hào)：O157.5

文獻(xiàn)標(biāo)志碼：A

Padamkar-Ivan指數(shù)是2000年P(guān)adamkar V Khadikar提出的一個(gè)新的拓?fù)渲笖?shù)，并將其縮寫為PI指數(shù)。PI指數(shù)對(duì)刻畫分子圖以及建立分子結(jié)構(gòu)與特征之間的關(guān)系具有重要作用，同時(shí)被廣泛應(yīng)用于預(yù)測(cè)化合物的物理、化學(xué)性質(zhì)及生物活性。文獻(xiàn)［1-4］陸續(xù)得到了雙圈圖和三圈圖的PI極值，文獻(xiàn)［5-8］分別得到了苯類烴分子圖、環(huán)形六面體、乘積圖、橋圖和鏈圖等特殊圖類的PI指數(shù)。本文選擇了齒輪圖和齒輪圖的一致膨脹圖這兩類特殊圖進(jìn)行研究，計(jì)算它們的PI指數(shù)。

1? 相關(guān)定義

定義1［9-10］? 設(shè)G為簡(jiǎn)單連通圖，V（G）表示其頂點(diǎn)集，E（G）表示其邊集。e∈E（G）是連接V（G）中點(diǎn)u和點(diǎn)v的一條邊，記作e=uv。一條邊到一個(gè)頂點(diǎn)的距離就是該點(diǎn)與該邊的兩個(gè)端點(diǎn)之間的最小距離。設(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è)圖G的PI指數(shù)定義為

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

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

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

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

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

定義6［14］? 設(shè)圖G是一個(gè)連通的簡(jiǎn)單圖，對(duì)任意的邊e=uv∈E（G），定義ne為G中與點(diǎn)u和點(diǎn)v距離不相等的邊數(shù)。

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

2? 主要結(jié)果

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

證明? 設(shè)齒輪圖G2n+1的頂點(diǎn)集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），容易驗(yàn)證其頂點(diǎn)數(shù)為2n+1，邊數(shù)為3n。記E1（G2n+1）={v0vi|i=1，2，…，n}，E2（G2n+1）=E（G2n+1）/E1（G2n+1）并設(shè)PIi=∑e∈Ei（G2n+1） [nev（e|G2n+1）+neu（e|G2n+1）]，其中i=1，2。

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

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

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

定理2? 設(shè)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}，頂點(diǎn)vi分別對(duì)應(yīng)UFG2n+1中的頂點(diǎn)集Vi（i=0，1，2，…，n），頂點(diǎn)ui分別對(duì)應(yīng)頂點(diǎn)集Ui（i=1，2，…，n）。對(duì)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可以發(fā)現(xiàn)圖UFG2n+1也存在對(duì)稱性，故在以下的證明過程中，可將圖UFG2n+1的邊分為5類。

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

（1）e∈[Vi，Vi]（i=1，2），設(shè)e=vijvil（j，l=1，2，…，t，且j≠l）。易證，在UFG2n+1中與e關(guān)聯(lián)的邊到點(diǎn)vij和點(diǎn)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），設(shè)e=uijuil（j，l=1， 2，…，t，且j≠l）。易證，在UFG2n+1中與e關(guān)聯(lián)的邊到點(diǎn)uij和點(diǎn)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]，設(shè)e=v0jv0l（j，l=1，2，…，t，且j≠l）。易證，在UFG2n+1中與e關(guān)聯(lián)的邊到點(diǎn)v0j和點(diǎn)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），設(shè)e=vijukl（j，l=1，2，…，t，且j≠l）。易證，在UFG2n+1中與e關(guān)聯(lián)的邊到點(diǎn)vij和點(diǎn)ukl的距離均不相等，因此

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

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

在UFG2n+1中不與e關(guān)聯(lián)且到點(diǎn)vij和點(diǎn)ukl的距離不相等的邊數(shù)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），設(shè)e=vijv0l（j，l=1，2，…，t，且j≠l）。易證，在UFG2n+1中與e關(guān)聯(lián)的邊到點(diǎn)vij和點(diǎn)v0l的距離均不相等，因此

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

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

在UFG2n+1中不與e關(guān)聯(lián)且到點(diǎn)vij和點(diǎn)v0l的距離不相等的邊數(shù)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）對(duì)n=3，情形（1）、情形（2）與上述相同，以下討論情形（3）、（4）、（5）。

（1）e∈[V0，V0]，設(shè)e=v0jv0l（j，l=1，2，…，t，且j≠l）。易證，在UFG2n+1中與e關(guān)聯(lián)的邊到點(diǎn)v0j和點(diǎn)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），設(shè)e=vijukl（j，l=1，2，…，t，且j≠l）。易證，在UFG2n+1中與e關(guān)聯(lián)的邊到點(diǎn)vij和點(diǎn)ukl的距離均不相等，因此

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

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

在UFG2n+1中不與e關(guān)聯(lián)且到點(diǎn)vij和點(diǎn)ukl的距離不相等的邊數(shù)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），設(shè)e=vijv0l（j，l=1，2，…，t，且j≠l）。易證，在UFG2n+1中與e關(guān)聯(lián)的邊到點(diǎn)vij和點(diǎn)v0l的距離均不相等，因此

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

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

在UFG2n+1中不與e關(guān)聯(lián)且到點(diǎn)vij和點(diǎn)v0l的距離不相等的邊數(shù)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）下設(shè)n≥4，以下只討論后3種情形。

（1）e∈[V0，V0]，設(shè)e=v0jv0l（j，l=1，2，…，t，且j≠l）。在UFG2n+1中與e關(guān)聯(lián)的邊到點(diǎn)v0j和點(diǎn)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），設(shè)e=vijukl （j，l=1，2，…，t，且j≠l）。易證，在UFG2n+1中與e關(guān)聯(lián)的邊到點(diǎn)vij和點(diǎn)ukl的距離均不相等，因此

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

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

在UFG2n+1中不與e關(guān)聯(lián)且到點(diǎn)vij和點(diǎn)ukl的距離不相等的邊數(shù)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），設(shè)e=vijv0l （j，l=1，2，…，t，且j≠l）。易證，在UFG2n+1中與e關(guān)聯(lián)的邊到點(diǎn)vij和點(diǎn)v0l的距離均不相等，因此

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

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

=（n+5）t－4；

在UFG2n+1中不與e關(guān)聯(lián)且到點(diǎn)vij和點(diǎn)v0l的距離不相等的邊數(shù)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? 結(jié)論

本文利用圖的對(duì)稱性，將復(fù)雜圖的邊分類來討論各自的PI值。通過將齒輪圖的一致膨脹圖與原圖進(jìn)行類比，把結(jié)構(gòu)較為簡(jiǎn)單的原圖中計(jì)算PI指數(shù)的方法運(yùn)用到結(jié)構(gòu)較為復(fù)雜的一致膨脹圖中，得到了齒輪圖及其一致膨脹圖的PI指數(shù)公式。

參考文獻(xiàn)：

[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．

（責(zé)任編輯：曾? 晶）

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