齿轮图及其一致膨胀图的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