路与广义Petersen图的直积图的Wiener指数.pdf

第41卷第2期2024年3月新疆大学学报（自然科学版中英文）Journal of Xinjiang University(Natural Science Edition in Chinese and English)Vol.41,No.2Mar.,2024路与广义Petersen图的直积图的Wiener指数白明鹭，田应智(新疆大学 数学与系统科学学院，新疆 乌鲁木齐 830017)摘要：图 G 和 H 的直积图 GH 是一个顶点集为 V(G)V(H)的图,两点(g1,h1)和(g2,h2)是相邻的当且仅当g1g2是图 G 中的一条边,h1h2是图 H 中的一条边.连通图 G 的 Wiener 指数,记作 W(G),是图 G 中无序点对之间的距离之和.最后得到了路与广义 Petersen 图 P(m,3)的直积图的 Wiener 指数.关键词：Wiener 指数;直积;路;广义 Petersen 图DOI：10.13568/ki.651094.651316.2023.04.13.0002中图分类号：O157.5文献标识码：A文章编号：2096-7675(2024)02-0218-010引文格式：白明鹭，田应智 路与广义Petersen 图的直积图的Wiener 指数J 新疆大学学报(自然科学版中英文)，2024，41(2)：218-227英文引文格式：BAI Minglu，TIAN Yingzhi Wiener index of the direct product of a path and a generalized PetersengraphJ Journal of Xinjiang University(Natural Science Edition in Chinese and English)，2024，41(2)：218-227Wiener Index of the Direct Product of a Path and aGeneralized Petersen GraphBAI Minglu,TIAN Yingzhi(School of Mathematics and System Sciences,Xinjiang University,Urumqi Xinjiang 830017,China)Abstract：For two graphs G and H,the direct product GH is the graph with vertex set V(G)V(H)and twovertices(g1,h1)and(g2,h2)are adjacent whenever g1g2is an edge in G and h1h2is an edge in H.The Wienerindex of a connected graph G,denoted by W(G),is the sum of the distances between all unordered pairs of verticesof G.In this paper,we obtain the Wiener index of the direct product of a path and a generalized Petersen graphP(m,3).Key words：Wiener index;direct product;paths;generalized Petersen graphs0引 言本文所有涉及到的定义和符号,参见文献1.图G和H的直积图(也被称为Kronecker积,张量积等),记为GH,其顶点集为V(GH)=V(G)V(H),两个顶点(g1,h1)和(g2,h2)相邻当且仅当g1g2 E(G)且h1h2 E(H).Weichsel2证明了两个非平凡的连通图G与H的直积图是连通的当且仅当G与H中至少有一个包含奇圈.许多学者对直积进行了研究,如吴丽芸等3研究了路和圈、圈和圈的直积图的超点连通性.有关直积图的更多结果可参阅文献4.连通图G的Wiener指数是指图G中无序点对之间的距离之和,即W(G)=(1/2)Pg1,g2V(G)dG(g1,g2).这一指数概念由Wiener5于1947年提出,在物理化学研究和通讯网络中有大量的应用.物理化学研究中,Wiener指数可以预测化合物的沸点,还可以反映分子表面积对体积的比例.Wiener指数最新的应用是合理化氯苯电解还原的机制原理,区分富勒烯的同分异构体.此外,与之密切相关的另一个概念:平均距离,表示图中所有无序顶点对之间距离的平均值.这一概念被用于计算机系统连通及通讯网络的分析和设计中.总之,Wiener指数已得到广大图论工作者的重视并被广泛研究.由直积方法构造出的大图,继承了因子图的优良性质.因此研究不同类型因子图的直积图的Wiener指数具有理论和现实意义.一些学者对此进行研究,如Hoji等6确定了连通图G与完全图Kn(n3)的直积图GKn收稿日期：2023-04-13基金项目：国家自然科学基金“点（边）-k-极大r-一致超图的边数研究”（12261086）作者简介：白明鹭（1998），女，硕士生，从事图论及其应用的研究，E-mail：通讯作者：田应智（1983），男，博士，教授，主要从事图论及其应用的研究，E-mail：第2期白明鹭，等：路与广义Petersen图的直积图的Wiener指数219的Wiener指数,Pattabiraman等7得到连通图G与完全多部图Km0,m1,mr1的直积图GKm0,m1,mr1的Wiener指数.在文献8中,Pattabiraman等给出了路和圈的直积图的Wiener指数,随后Pattabiraman得到了一个偶圈和一个奇圈,以及两个奇圈的直积图的Wiener指数9.本文在现有基础上研究路和一类广义Petersen图P(m,3)的直积图的Wiener指数.广义Petersen图由Coxeter10于1950年引入,是一类重要且被广泛研究的图类11.本文主要结合路与广义Petersen图P(m,3)的特性,利用理论计算的方法研究并得出其直积图的Wiener指数,得到的Wiener指数仅需要用两个因子图的阶数就可表示出来.本文的研究为后续计算路和一般的广义Petersen图P(m,a)的Wiener指数提供了研究思路.1预备知识广义Petersen图,记为G=P(m,a),其顶点集为V(G)=U W,其中U=u0,u1,um1为外圈点集,W=w0,w1,wm1为内圈点集;其边集为E(G)=uiwi,uiui+1,wiwi+a|0im1,其中下标取模m运算且m5,0am.当m=5,a=2时,广义Petersen图P(m,a)就是著名的Petersen图.对于G中的两个顶点g1和g2,dG(g1,g2)是点g1和g2之间的距离.图G中连接g1和g2的最短奇途径的长度,记为odG(g1,g2);图G中连接g1和g2的最短偶途径的长度,记为edG(g1,g2).如果在图G中g1和g2之间没有奇长或偶长的途径,则我们认为odG(g1,g2)=或edG(g1,g2)=.若无歧义,可删除dG(g1,g2),odG(g1,g2),edG(g1,g2)中的下标G.设Pr是阶数为r的路,其点集为V(Pr)=x0,x1,xr1.我们记Xi=xiV(P(m,a),i=0,1,r1,称Xi为PrP(m,a)的第i层.将点(xi,uj)和点(xi,wj)分别简记为xi,j和yi,j,则Xi中的点为xi,j,yi,j|0j m1.因此,我们很容易得到V(PrP(m,a)=V(Pr)V(P(m,a)=r1i=0Xi.引理112对于图G和H的直积图GH,它的两个顶点(g1,h1)和(g2,h2)间距离为dGH(g1,h1),(g2,h2)=minmaxodG(g1,g2),odH(h1,h2),maxedG(g1,g2),edH(h1,h2).接下来,我们想要确定广义Petersen图P(m,3)中任意两个顶点间的最短奇(偶)途径的长度.若m是偶数,则P(m,3)不含奇圈,PnP(m,3)不连通.所以我们仅考虑m为奇数的情况.由P(m,3)的定义和旋转对称性的特殊结构,可将点uj固定在点u0,点wj固定在点w0.因此,我们不需要计算任意两个顶点间的最短奇(偶)途径的长度,仅需计算u0和w0到每个顶点间的最短奇(偶)途径的长度.又因为P(m,3)是关于u0和w0对称的,故仅考虑u0和w0到点uj,wj|0j m/2的最短奇(偶)途径的长度(u0和w0到点umj,wmj|0j m/2的最短奇(偶)途径的长度证明类似).引理2设m是一个正奇数且m 0 mod(3),P(m,3)是一个广义Petersen图,其点集为U W,U=u0,u1,um1,W=w0,w1,wm1,则除了od(u0,u1)=1,ed(u0,u2)=2,从点u0和点w0到点uj,wj|0j m/2的最短奇(偶)途径的长度为od(u0,uj)=j3+2,j 0 mod(3),j3是奇的m3j3+2,j 0 mod(3),j3是偶的m3j3+3,j 1 mod(3),j3是奇的j3+3,j 1 mod(3),j3是偶的m3j3+3,j 2 mod(3),j3是奇的j3+3,j 2 mod(3),j3是偶的(1)ed(u0,uj)=m3j3+2,j 0 mod(3),j3是奇的j3+2,j 0 mod(3),j3是偶的j3+3,j 1 mod(3),j3是奇的m3j3+3,j 1 mod(3),j3是偶的j3+3,j 2 mod(3),j3是奇的m3j3+3,j 2 mod(3),j3是偶的(2)220新疆大学学报（自然科学版中英文）2024年od(u0,wj)=od(w0,uj)=m3j3+1,j 0 mod(3),j3是奇的j3+1,j 0 mod(3),j3是偶的j3+2,j 1 mod(3),j3是奇的m3j3+2,j 1 mod(3),j3是偶的j3+2,j 2 mod(3),j3是奇的m3j3+2,j 2 mod(3),j3是偶的(3)ed(u0,wj)=ed(w0,uj)=j3+1,j 0 mod(3),j3是奇的m3j3+1,j 0 mod(3),j3是偶的m3j3+2,j 1 mod(3),j3是奇的j3+2,j 1 mod(3),j3是偶的m3j3+2,j 2 mod(3),j3是奇的j3+2,j 2 mod(3),j3是偶的(4)od(w0,wj)=j3,j 0 mod(3),j3是奇的m3j3,j 0 mod(3),j3是偶的m3j3+3,j 1 mod(3),j3是奇的j3+3,j 1 mod(3),j3是偶的m3j3+3,j 2 mod(3),j3是奇的j3+3,j 2 mod(3),j3是偶的(5)ed(w0,wj)=m3j3,j 0 mod(3),j3是奇的j3,j 0 mod(3),j3是偶的j3+3,j 1 mod(3),j3是奇的m3j3+3,j 1 mod(3),j3是偶的j3+3,j 2 mod(3),j3是奇的m3j3+3,j 2 mod(3),j3是偶的(6)证明 当m0 mod(3),内圈点导出的子图为3个长度均为m/3的圈的集合.首先计算点u0到点uj的最短奇、偶途径的长度.若j 0 mod(3),点u0沿着对应边u0w0,然后通过内圈边捷径到达点wj,再沿着对应边wjuj到达点uj,则存在两条奇偶性不同且长度分别为(j/3)+2和(m/3)(j/3)+2的u0uj途径.若j 1 mod(3),点u0需要先到达点w3j/3,再沿着对应边u3j/3w3j/3和外圈边u3j/3uj到达点uj,则存在两条奇偶性不同且长度分别为j/3+3和(m/3)j/3+3的u0uj途径.若j 2 mod(3),点u0需要先到达点w3j/3,再沿着对应边u3j/3w3j/3和外圈边u3j/3uj到达点uj,则存在两条奇偶性不同且长度分别为j/3+3和(m/3)j/3+3的u0uj途径.必须注意特殊情况:od(u0,u1)=d(u0,u1)=1和ed(u0,u2)=d(u0,u2)=2.接下来,计算点w0到点wj的最短奇、偶途径的长度.若j 0 mod(3),点w0沿着内圈边到达点wj,则存在两条奇偶性不同且长度分别为j/3和(m/3)(j/3)的w0wj途径.若j 1 mod(3),点w0需要先沿着内圈边到达点w3j/3,再沿着两条对应边u3j/3w3j/3,ujwj和外圈边u3j/3uj到达点wj,则存在两条奇偶性不同且长度分别为j/3+3和(m/3)j/3+3的w0wj途径.若j 2 mod(3),点w0需要先沿着内圈边到达点w3j/3,再沿着两条对应边u3j/3w3j/3,ujwj和外圈边u3j/3uj到达点wj,则存在两条奇偶性不同且长度分别为j/3+3和(m/3)j/3+3的w0wj途径.现在研究两个点在不同的圈中的情形,即点u0到点wj和点w0到点uj.对于点u0到点wj,证明与u0到uj的情况类似,只是不需要对应边ujwj或u3j/3w3j/3或u3j/3w3j/3.对于点w0到点uj,可以用类似的方法进行推导.由于广义Petersen图P(m,3)的特殊结构,上面构造的奇、偶途径都是最短的.第2期白明鹭，等：路与广义Petersen图的直积图的Wiener指数2212主要结果定理1设m是正奇数且m0 mod(3),n是正整数,则G=P2nP(m,3)的Wiener指数为(i)W(G)=(4m3n2/3)+16m2n2+(8n432n3+50n256n+20)m,1n(m/6)+(1/2);(ii)W(G)=(m5/162)+(4n/27)(4/27)m4+(8n/3)(25/18)m3+(16/3)n3+(50/3)n(17/3)m2+(22n+12)m,n(m/6)+(3/2).证明 记P2n的点为xi|0i2n1,P(m,3)的点为uj,wj|0j m1,则直积图G=P2nP(m,3)的点记为xi,j,yi,j|0i2n1,0j m1,其中xi,j和yi,j分别表示点(xi,uj)和点(xi,wj).记Sk,j表示点xk,j到图G其余所有点的距离之和,Sk,j表示点yk,j到图G其余所有点的距离之和,即Sk,j=PvV(G)dG(xk,j,v),Sk,j=PvV(G)dG(yk,j,v).由于P(m,3)的定义及其旋转对称性的特殊结构,使得Sk,j=Sk,l,Sk,j=Sk,l.所以,我们仅需计算Sk,0和Sk,0对于k=0,1,2n1,再将计算结果乘以m即可求得Pm1j=0Sk,j与Pm1j=0Sk,j.由于G存在对称性,所以n1Xk=0m1Xj=0Sk,j=n1Xk=0m1Xj=0S2n(k+1),j,n1Xk=0m1Xj=0Sk,j=n1Xk=0m1Xj=0S2n(k+1),j,从而2n1Xk=0m1Xj=0Sk,j=2n1Xk=0m1Xj=0Sk,j,2n1Xk=0m1Xj=0Sk,j=2n1Xk=0m1Xj=0Sk,j.因此,W(G)可用下面的形式表示,即W(G)=m(n1Xk=0Sk,0+n1Xk=0Sk,0)(7)所以证明的重点是计算Pn1k=0Sk,0和Pn1k=0Sk,0.对于Pn1k=0Sk,0(Pn1k=0Sk,0以同样的方式进行计算),我们划分G的点集V(G)=2n1i=0Xi为ki=0Xi和2n1i=k+1Xi,并单独计算.对于每个k与i,PvXidG(xk,0,v)满足下面的式子.XvXidG(xk,0,v)=m1Xj=0dG(xk,0,xi,j)+m1Xj=0dG(xk,0,yi,j)=2(m12Xj=1dG(xk,0,xi,j)+m12Xj=1dG(xk,0,yi,j)+dG(xk,0,xi,0)+dG(xk,0,yi,0).接着,对于固定的k和i,要计算点xk,0到图G的第i层Xi中所有点的距离和,即求PvXidG(xk,0,v).我们仅考虑(m/6)(1/2)是奇数的情形,即m=9,21,33,.(m/6)(1/2)是偶数的情形,即m=15,27,39,可同样证明)而由|ki|的奇偶性,我们分以下两种情形计算.情形1|ki|是偶数.在情形1中,需要寻找从点u0到点uj和点wj(0j m/2)的最短偶途径,如式(2)和式(4)所示.由引理1,有d(xk,0,xi,j)=max|ki|,ed(u0,uj),d(xk,0,yi,j)=max|ki|,ed(u0,wj).由引理2,可根据j的值,分以下六种情形来讨论dG(xk,0,xi,j)和dG(xk,0,yi,j).1)j 0 mod(3)且j/3是奇的,即j/3=1,3,(m/6)(1/2)(j=3,9,(m/2)(3/2).因此ed(u0,uj)=(m/3)(j/3)+2=(m/6)+(5/2),(m/6)+(9/2),(m/3)+1;ed(u0,wj)=(j/3)+1=2,4,(m/6)+(1/2),所以可计算点xk,0到第i层符合j条件的点的距离和,即Xj3是奇的,1 j3m612dG(xk,0,xi,j)=(m6+52)+(m6+92)+(m3+1),|ki|m3+1(8)222新疆大学学报（自然科学版中英文）2024年Xj3是奇的1 j3m612dG(xk,0,yi,j)=2+4+(m6+12),|ki|=0|ki|(|ki|22+1)+(|ki|+2)+(|ki|+4)+(m6+12),2|ki|m6+12|ki|(m12+14),|ki|m6+12(9)式(8)的解释如下:当|ki|(m/3)+1时,d(xk,0,xi,j)=|ki|,则从点xk,0到点xi,3,xi,9,xi,(m/2)(3/2)的距离和为|ki|(m/12)+(1/4).对于式(9),点xk,0到点yi,3,yi,9,yi,(m/2)(3/2)距离的选择与上面的论述类似,不再赘述.下面论述点xk,0到不同类型j的点xi,j与点yi,j的距离,其距离的选择与上面的论述类似,因此不再赘述,将直接给出结果.2)j 0 mod(3)且j/3是偶的,即j/3=2,4,(m/6)(3/2)(j=6,12,(m/2)(9/2).因此ed(u0,uj)=(j/3)+2=4,6,(m/6)+(1/2),ed(u0,wj)=(m/3)(j/3)+1=(m/6)+(5/2),(m/6)+(9/2),(m/3)1.(注意j/3=0的情形也符合这一规律,但是为了之后计算方便,这种情况被单独考虑)所以可计算点xk,0到第i层符合j条件的点的距离和,即Xj3是偶的2 j3m632dG(xk,0,xi,j)=4+6+(m6+12),|ki|m6+12(10)Xj3是偶的2 j3m632dG(xk,0,yi,j)=(m6+52)+(m6+92)+(m31),|ki|m31(11)dG(xk,0,xi,0)+dG(xk,0,yi,0)=(|ki|+(m3+1),0|ki|m3+12|ki|,|ki|m3+1(12)对于式(10)和(11),分别得到了从点xk,0到点xi,6,xi,12,xi,(m/2)(9/2)和点yi,6,yi,12,yi,(m/2)(9/2)的距离和,而式(12)是点xk,0到点xi,0与点yi,0的距离和.3)j 1 mod(3)且j/3是奇的,即j/3=1,3,(m/6)(1/2)(j=4,10,(m/2)(1/2).因此ed(u0,uj)=j/3+3=4,6,(m/6)+(5/2),ed(u0,wj)=(m/3)j/3+2=(m/6)+(5/2),(m/6)+(9/2),(m/3)+1.所以可计算点xk,0到第i层符合j条件的点的距离和,即Xj3是奇的1 j3 m612dG(xk,0,xi,j)=4+6+(m6+52),|ki|m6+52(13)式(13)是点xk,0到点xi,4,xi,10,xi,(m/2)(1/2)的距离和,而点xk,0到点yi,4,yi,10,yi,(m/2)(1/2)的距离和的表达式与式(8)相同.第2期白明鹭，等：路与广义Petersen图的直积图的Wiener指数2234)j 1mod(3)且j/3是偶的,即j/3=0,2,(m/6)(3/2)(j=1,7,(m/2)(7/2).因此ed(u0,uj)=(m/3)j/3+3=(m/6)+(9/2),(m/6)+(13/2),(m/3)+3,ed(u0,wj)=j/3+2=2,4,(m/6)+(1/2).所以可计算点xk,0到第i层符合j条件的点的距离和,即Xj3是偶的0 j3 m632dG(xk,0,xi,j)=(m6+92)+(m6+132)+(m3+3),|ki|m3+3(14)式(14)是点xk,0到点xi,1,xi,7,xi,(m/2)(7/2)的距离和,而点xk,0到点yi,1,yi,7,yi,(m/2)(7/2)的距离和的表达式与式(9)相同.5)j 2 mod(3)且j/3是奇的,即j/3=1,3,(m/6)(1/2)(j=2,8,(m/2)(5/2).除了特殊情况当j/3=1时,有e(u0,u2)=2;其余当j/3 1时,有ed(u0,uj)=j/3+3=6,8,(m/6)+(5/2),ed(u0,wj)=(m/3)j/3+2=(m/6)+(5/2),(m/6)+(9/2),(m/3)+1.所以可计算点xk,0到第i层符合j条件的点的距离和,即Xj3是奇的1 j3 m612dG(xk,0,xi,j)=2+(6+8+(m6+52),|ki|m6+52(15)式(15)是点xk,0到点xi,2,xi,8,xi,(m/2)(5/2)的距离和,而点xk,0到点yi,2,yi,8,yi,(m/2)(5/2)的距离和的结果与式(8)相同.6)j 2 mod(3)且j/3是偶的,即j/3=2,4,(m/6)(3/2)(j=5,11,(m/2)(11/2).因此ed(u0,uj)=(m/3)j/3+3=(m/6)+(9/2),(m/6)+(13/2),(m/3)+1,ed(u0,wj)=j/3+2=4,6,(m/6)+(1/2).此时可计算点xk,0到第i层符合j条件的点的距离和,即Xj3是偶的0 j3 m632dG(xk,0,xi,j)=(m6+92)+(m6+132)+(m3+1),|ki|m3+1(16)式(16)是点xk,0到点xi,5,xi,11,xi,(m/2)(11/2)的距离和,而点xk,0到点yi,5,yi,11,yi,(m/2)(11/2)的距离和的表达式与式(10)相同.于是,我们按(j/3),j/3和j/3的奇偶性进行分类分别得到点xk,0到点xi,j和yi,j的距离和.接下来,我们求点xk,0到第i层所有点的距离和,即PvXidG(xk,0,v).下面我们分三种子情形计算.子情形1.1当|ki|=0或2时,有PvXidG(xk,0,v)=|ki|+(m2/3)+(13/3)m6.子情形1.2当4|ki|(m/3)+1时,有PvXidG(xk,0,v)=3|ki|213|ki|+(m2/3)+(13/3)m+14.子情形1.3当|ki|(m/3)+1时,有PvXidG(xk,0,v)=2m|ki|.情形2|ki|是奇数.在情形2中,需要寻找从点u0到点uj和点wj(0j m/2)的最短奇途径,如式(1)和式(3)所示.由引理1可知d(xk,0,xi,j)=max|ki|,od(u0,uj)和d(xk,0,yi,j)=max|ki|,od(u0,wj).故使用与|ki|是偶数情形相同的方法,可以分别得到六种情形下点xk,0到点xi,j和yi,j的距离和,从而可以计算出点xk,0到第i层所有点的距离和PvXidG(xk,0,v),下面直接给出|ki|是奇数时PvXidG(xk,0,v)的结果.子情形2.1当|ki|=1时,有PvXidG(xk,0,v)=(1/3)m2+(13/3)m4.子情形2.2当3|ki|(m/3)时,有PvXidG(xk,0,v)=3|ki|213|ki|+(1/3)m2+(13/3)m+14.224新疆大学学报（自然科学版中英文）2024年子情形2.3当|ki|(m/3)时,有PvXidG(xk,0,v)=2m|ki|.此时我们已经得到了从顶点xk,0到第i层Xi中所有点的距离之和,即PvXidG(xk,0,v).接下来,我们将分别计算点xk,0到ki=0Xi和2n1i=k+1Xi这两部分所有点的距离和.对于计算Pv Xi,0 i k.dG(xk,0,v),我们分下面四种情形考虑.(I)k=0.Pv Xi,0 i kdG(xk,0,v)=13m2+133m6.(II)k=1.Pv Xi,0 i kdG(xk,0,v)=23m2+263m10.(III)2k(m/3).Xv Xi,0 i kdG(xk,0,v)=(13m2+133m6)+2(13m2+133m4)+Xv Xi,0 i k3(3i2+(6k+13)i+3k213k+13m2+133m+14)=k35k2+(13m2+133m+8)k+13m2+133m18.(IV)k(m/3)+1.Xv Xi,0 i kdG(xk,0,v)=(13m2+133m6)+2(13m2+133m4)+Xv Xi,k(m3+1)i k3(3i2+(6k+13)i+3k213k+13m2+133m+14)+Xv Xi,0 i k(m3+2)(2mi+2km)=mk2+mk+127m3+89m2+7m14.对于计算Pv Xi,k+1 i 2n1dG(xk,0,v),我们考虑下面三种情形.(V)k(m/3)+2n2.Xv Xi,k+1 i 2n1dG(xk,0,v)=2(13m2+133m4)+Xv Xi,k+3 i k+m3+1(3i2+(6k13)i+3k213k+13m2+133m+14)+Xv Xi,k+m3+2 i 2n1(2mi2km)=mk2+(4nm+m)k+127m3+59m2+(4n22n+83)m8.第2期白明鹭，等：路与广义Petersen图的直积图的Wiener指数225(VI)(m/3)+2n1k2n3.Xv Xi,k+1 i 2n1dG(xk,0,v)=2(13m2+133m4)+Xv Xi,k+3 i 2n1(3i2+(6k13)i+3k213k+13m2+133m+14)=k3+(6n8)k2+(13m2133m12n2+32n21)k+(23n13)m2+(263n133)m+8n332n2+42n26.(VII)k=2n2.Pv Xi,k+1 i 2n1dG(xk,0,v)=13m2+133(m4).根据(I)(VII),按n的取值进行分类,得到Pn1k=0Sk,0的表达式如下当n=1时,有n1Pk=0Sk,0=(2/3)m2+(26/3)m10.当2n(m/6)+(1/2)时,有n1Xk=0Sk,0=n1Xk=0Xv Xi,0 i kdG(xk,0,v)+n1Xk=0Xv Xi,k+1 i 2n1dG(xk,0,v)=(13m2+133m6)+(23m2+263m10)+n1Xk=2(k35k2+(13m2+133m+8)k+13m2+133m18)+n1Xk=0(k3+(6n8)k2(13m2+133m+12n232n+21)k+(23n13)m2+(263n133)m+8n332n2+42n26)=23m2n2+263mn2+4n4523n3+27n21193n+16.当(m/6)+(3/2)n(m/3)+1时,有n1Xk=0Sk,0=n1Xk=0Xv Xi,0 i kdG(xk,0,v)+n1Xk=0Xv Xi,k+1 i 2n1dG(xk,0,v)=(13m2+133m6)+(23m2+263m10)+n1Xk=2(k35k2+(13m2+133m+8)k+13m2+133m18)+m3+2n2Xk=0(mk2+(4nm+m)k+127m3+59m2+(4n22n+83)m8)+n1Xk=m3+2n1(k3+(6n8)k2(13m2+133m+12n232n+21)k+(23n13)m2+(263n133)m+8n332n2+42n26)=1324m4+(227n13162)m3+(139n34)m2+(83n3+9n5318)m22n+12.226新疆大学学报（自然科学版中英文）2024年当n(m/3)+2时,有n1Xk=0Sk,0=n1Xk=0Xv Xi,0 i kdG(xk,0,v)+n1Xk=0Xv Xi,k+1 i 2n1dG(xk,0,v)=(13m2+133m6)+(23m2+263m10)+m3Xk=2(k35k2+(13m2+133m+8)k+13m2+133m18)+n1Xk=m3+1(mk2+mk+127m3+89m2+7m14)+n1Xk=0(mk2+(4nm+m)k+127m3+59m2+(4n22n+83)m8)=1324m4+(227n13162)m3+(139n34)m2+(83n3+9n5318)m22n+12.整理并合并上述表达式,可得到Pn1k=0Sk,0的最终结果如下当1n(m/6)+(1/2)时,n1Pk=0Sk,0=(2/3)m2n2+(26/3)mn2+4n4(52/3)n3+27n2(119/3)n+16.当n(m/6)+(3/2)时,n1Pk=0Sk,0=(m4/324)+(2n/27)(13/162)m3+(13n/9)(3/4)m2+(8/3)n3+9n(53/18)m22n+12.而计算Pn1k=0Sk,0时,运用的方法与理论和计算Pn1k=0Sk,0类似,故直接给出其计算结果如下当1n(m/6)+(1/2)时,n1Pk=0Sk,0=(2/3)m2n2+(22/3)mn2+4n4(44/3)n3+23n2(49/3)n+4.当n(m/6)+(3/2)时,n1Pk=0Sk,0=(m4/324)+(2n/27)(11/162)m3+(11n/9)(23/36)m2+(8/3)n3+(23/3)n(49/18)m.由式(7),我们可以得到这个定理的结果.定理2设m是正奇数且m0 mod(3),n是正整数,则G=P2n+1P(m,3)的Wiener指数为(i)W(G)=(4/3)n2+(4/3)n+(1/3)m3+(16n2+16n+4)m2+(8n416n3+14n226n+1)m,1n(m/6)+(1/2);(ii)W(G)=(m5/162)+(4n/27)(2/27)m4+(8n/3)(1/18)m3+(16/3)n3+8n2+(62/3)n+(10/3)m2+(22n+1)m,n(m/6)+(3/2).证明 路的阶数为2n+1,故由G的对称性有下面的表达式n1Xk=0m1Xj=0Sk,j=n1Xk=0m1Xj=0S2nk,j2nXk=0m1Xj=0Sk,j=2n1Xk=0m1Xj=0Sk,j+m1Xj=0Sn,j,Sk,j也有相同的性质.故W(G)可用下面的形式表示,即W(G)=m(n1Xk=0Sk,0+n1Xk=0Sk,0)+m2(Sn,0+Sn,0).对于Sk,0,Sk,0及Sn,0,Sn,0的计算,我们使用与定理1相似的分析方法,除了点xk,0到2ni=k+1Xi的距离和,i的取值应从k+1到2n1变为k+1到2n.通过与定理1几乎相同的论证,我们可以得到这个定理的结果.故对证明细节不再重复叙述.定理3设m是正奇数且m1 mod(3),n是正整数,则G=P2nP(m,3)的Wiener指数为(i)W(G)=(4m3n2)/3)+16m2n2+(8n432n3+(128/3)n256n+20)m,1n(m/6)+(5/6);(ii)W(G)=(m5/162)+(4n/27)(4/27)m4+(8n/3)(32/27)m3+(16/3)n3+(128/9)n(292/81)m2+(928n/27)+(305/18)m,n(m/6)+(5/6).定理4设m是正奇数且m1 mod(3),n是正整数,则G=P2n+1P(m,3)的Wiener指数为第2期白明鹭，等：路与广义Petersen图的直积图的Wiener指数227(i)W(G)=(4/3)n2+(4/3)n+(1/3)m3+(16n2+16n+4)m2+(8n416n3+(20/3)n2(100/3)n(1/3)m,1n(m/6)+(5/6);(ii)W(G)=(m5/162)+(4/27)n(2/27)m4+(8n/3)+(4/27)m3+(16/3)n3+8n2+(164/9)n+(338/81)m2(928n/27)+(13/54)m,n(m/6)+(5/6).定理5设m是正奇数且m2 mod(3),n是正整数,则G=P2nP(m,3)的Wiener指数为(i)W(G)=(4m3n2/3)+16m2n2+(8n432n3+(140/3)n256n+20)m,1n(m/6)+(7/6);(ii)W(G)=(m5/162)+(4n/27)(4/27)m4+(8n/3)(35/27)m3+(16/3)n3+(140/9)n(410/81)m2+(692n/27)+(653/54)m,n(m/6)+(7/6).定理6设m是正奇数且m2 mod(3),n是正整数,则G=P2n+1P(m,3)的Wiener指数为(i)W(G)=(4/3)n2+(4/3)n+(1/3)m3+(16n2+16n+4)m2+(8n416n3+(32/3)n2(88/3)n(1/3)m,1n(m/6)+(7/6);(ii)W(G)=(m5/162)+(4n/27)(2/27)m4+(8n/3)+(1/27)m3+(16/3)n3+8n2+(176/9)n+(274/81)m2(692n/27)+(13/18)m,n(m/6)+(7/6).参考文献：1BONDY J A，MURTY U S RGraph theoryMLondon：Springer，20082WEICHSEL P MThe Kronecker product of graphsJProceedings of the American Mathematical Society，1962，13(1)：473吴丽芸，田应智 路和圈、圈和圈的Kronecker积图的超点连通性J 新疆大学学报(自然科学版)(中英文)，2022，39(2)：176-181WU L Y，TIAN Y ZSuper connected Kronecker products of paths，cycles and cyclesJJournal of Xinjiang University(NaturalScience Edition in Chinese and English)，2022，39(2)：176-181(in Chinese)4HAMMACK R，IMRICH W，KLAVZAR SHandbook of product graphsMBoca Raton：CRC Press，20115WIENER HStructural determination of paraffin boiling pointsJJournal of the American Chemical Society，1947，69(1)：17-206HOJI M，LUO Z Y，VUMAR EWiener and vertex PI indices of Kronecker products of graphsJDiscrete Applied Mathemat-ics，2010，158(16)：1848-18557PATTABIRAMAN K，PAULRAJA POn some topological indices of the tensor products of graphsJDiscrete Applied Math-ematics，2012，160(3)：267-2798PATTABIRAMAN K，PAULRAJA PWiener index of the tensor pr