路与圈的笛卡尔积的Wiener指数

张亚宾，叶永升，王 健

（淮北师范大学,安徽 淮北 235000）

0 引言

Wiener 指数（Wiener index）是由美国化学家H.Wiener 在1947 年提出的［1］，刚开始被用来预测石蜡的沸点，随后Wiener指数和分子团化学性质之间的联系被逐步发现。1976年，Wiener指数开始在数学上得到应用［2］，从此以后，Wiener指数开始引起了广大学者的关注和研究［3］，Darabi 等［4］研究了图的Wiener 指数与离心率之间的关系，Ervin Györi 等［5］证明了四边形图的Wiener 指数的上界，Duan S 等［6］给出了路的强积的Wiener 指数，王少辉等［7］给出了特殊图的Wiener 指数，Bapatr 等［8］发现扇图与轮图的笛卡尔积的拓性（Wiener）指数在各种化合物的分析过程中起重要作用，可见研究各类特殊图的笛卡尔积图的Wiener 指数对科研及日常应用具有重大意义［9］。本文主要研究Pn×Pm和Cn×Pm的Wiener指数。

1 预备知识

本文中所有的图都是简单无向图，对于图G，V(G)表示G的顶点集，E(G)表示G的边集。dG(v,u)表示图G中顶点v与u之间的最短距离，即连接u、v的最短路径的长度。此外，用Pn表示含有n个顶点的路图，记作Pn=u1u2…un，Cn表示含有n个顶点的圈图，记作Cn=x1x2…xn。

定义1［10］图G中顶点v到其他所有顶点的距离之和，记为dG(v)，即：

定义2［11］图G的Wiener指数是指图G中所有顶点对之间的距离和，记作W(G)，即：

定义3［12］设G1和G2是两个图，它的笛卡尔积用G1×G2表示，它的点集V(G1×G2)=V(G1)×V(G2)

边集E(G1×G2)={(u1,u2),(v1,v2)|u1=v1,u2v2∈E(G1)或u2=v2,u1v1∈E(G2)} 。如图1所示。

图1 P3×P4 和C3×P3

在文献［13］中给出了圈的Wiener指数，则有：

2 主要结果

于玲［14］用数学归纳法证明了Pn×Pm的Wiener指数，接下来采用将图分块的方法进行证明。

引理1对于图Pn×Pm，有

证明将图Pn×Pm记为图H。将图H中的第1行第1列的顶点记为v11，由定义1可知，顶点v11的Wiener指数为：

定理2设n，m为正整数，则有：

证明将图Pn×Pm记为图H，在图H中任取一点，记为vij，其中下标i表示第i行，下标j表示第j列，以顶点vij为中心，第i行和第j列为分割线，将图Pn×Pm分为4 个部分，分别记作H1、H2、H3、H4，如图2所示。……