星与路和完全图与路的笛卡尔积的Wiener指数

张亚宾，叶永升，王 健

（淮北师范大学 数学科学学院，安徽 淮北 235000）

0 引言

1947年，Wiener为研究烷烃分子沸点提出分子结构的描述符，现称为Wiener指数［1］。此后，众多的化学学者对Wiener指数进行研究，发现它能够揭示化学中分子之间的关系［2］，随着研究过程的深入，应用的数学方法也越来越多，数学家也成为研究这个重要指数的群体之一［3-6］。早期数学家主要研究一些简单特殊图的Wiener 指数［7］，而近年来，国内外有关学者为得到图G的Wiener 指数与图G的结构关系，利用图的笛卡尔积、强积等方式构造不同类型的图进行研究。比如Peterin等［8］给出图的强积的Wiener指数，Sumenjak 等［9］证明一个有向图的Wiener 指数的一个猜想，Ervin 等［10］研究四边形图的Wiener 指数，Donno［11］给出完全图环积的Wiener指数等。由于国内外有关学者对各种图的Wiener指数研究比较多，而图的笛卡尔积作为一种由小图构成的大图，它不仅拥有小图的全部性质，而且在各个方面更加优于小图，它有着重要的实际应用价值［12］。且Wiener指数作为化学和数学结合的产物，在数学上研究图的Wiener指数的计算公式可以推动相关领域的交叉学科研究，通过这些领域的交叉融合，可以探寻图的笛卡尔积Wiener 指数应用，建立更为完善的理论框架和研究系统［13］。所以研究图的笛卡尔积Wiener 指数有着理论意义和实际应用价值。

设Sm和Km分别为m个顶点的星图和完全图，Pn为含有n个顶点的路图，本文主要得到星图Sm与路Pn笛卡尔积和完全图Km与路Pn笛卡尔积Wiener指数的计算公式。

1 预备知识

本文中所有的图都是简单无向图，对于图G，V(G)表示G的顶点集，E(G)表示G的边集。dG(v,u)表示图G中顶点v与u之间的最短距离，即连接v，u的最短路径的长度。

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

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

定义3［16］设G1和G2是2个图，记G1×G2为笛卡尔积，则点集V(G1×G2)=V(G1)×V(G2)，边集

由定义可得：在图Sm×Pn中，将第i行和第j列的点uiwj，其中ui∈V(Sm)，wj∈V(Pn)，记作vij。当m=4，n=3 时，S4×P3和K4×P3结构图如图1所示。

图1 S4×P3 和K4×P3 的结构图

2 主要结果

首先给出图Sm×Pn的Wiener指数的证明，然后证明图Km×Pn的Wiener指数。

引理1对于图Sm×Pn，其中n，m为正整数，则有

证明将图Sm×Pn记为图G，图G中的第2行第1列的顶点记为v21，图G中的第1行第1列的顶点记为v11，由定义1可知，顶点v21和v11的Wiener指数为：

证明将图Sm×Pn记为图G，在图G中任取一点，记为vij，其中vij表示第i行、第j列的顶点。以顶点vij所在第j列为分割线将图Sm×Pn分为2个部分，分别记作图G1、图G2，将第1行所有顶点构成的图记为图G3，剩下的所有顶点构成的图记为图G4，将第j列上的所有点构成的图记作图Hj，如图2所示。

图2 Sm×Pn 的结构图

由图2和定义2可知，求顶点vij到图G中其他顶点的距离之和可以转化为求顶点vij到图G1和图G2这2个部分中所有的顶点的距离之和，此时注意到在计算过程中，第j列的顶点分别计算2次。

在图G1中，它是由行为m个顶点、列为j个顶点构成的笛卡尔积图，记作Sm×Pj，根据路的Wiener指数的对称性，当点vij在第1行时，点vij到图G1所有顶点的距离之和等于v11到图G1所有顶点的距离之和，即dG1(v11)=dG1(v1j)。当点vij不在第1行时，点vij到图G1所有顶点的距离之和等于v21到图G1所有顶点的距离之和，即dG1(v21)=dG1(vij)，根据引理1可知：

同理，在图G2中，有：

在图G中，点vij到第j列上的所有顶点的距离之和记作dHj(vij)，则：

即在图G中，点vij到其它所有顶点的距离之和为：

根据定义2可得

下面用同样的方法证明Km×Pn的Wiener指数。

证明在图Km×Pn中，将图Km×Pn记作图G′，第i行第1列的顶点记为vi1，根据完全图的Wiener指数的性质，任意一个顶点到其它顶点的距离之和都相同。则顶点vi1的Wiener指数与顶点v11的Wiener指数相等，有：

根据定义3可知，在图Km×Pn中，将第i行和第j列的点xiwj记作vij。接下来给出图Km×Pn的Wiener指数的证明。

证明将图Km×Pn记作图G′，由引理2可得，第i行第1列的点vi1的Wiener指数为

在图G′中，任取第j列，以第j列为界为分割线，将图G′分为2个部分，分别记作G′1、G′2。根据图的Wiener指数的对称性，可得：

完全图Km中的任一顶点到其它顶点的距离之和，记作dKm(vij)，即dKm(vij)=m-1。所以

在图G′中，

3 结论

本文利用路的对称性和图分块的技巧，将星图与路的笛卡尔积和完全图与路的笛卡尔积进行分块，得出Sm×Pn和Km×Pn的Wiener指数的计算公式，该公式将有助于快速准确地计算这2类图的Wiener指数，具有重要的理论和实际意义。而且本文利用特殊图的性质提出一种分块的方法，有望为其它图的笛卡尔积的Wiener指数研究提供更为可靠和实用的计算方法。