于 玲， 叶永升

(淮北师范大学 数学科学学院,安徽 淮北 235000)

路的笛卡尔积图的Wiener指数

于 玲， 叶永升

(淮北师范大学 数学科学学院,安徽 淮北 235000)

距离; 笛卡尔积; Wiener指数

0 引言

Wiener指数是化学研究中经典的拓扑指数(图不变量)之一,Wiener是由Harold Wiener[1]在1947年作为路径数目引入的,Wiener用它来研究石蜡的沸点,饱和碳氢化合物的结构以及性质之间的关系,分子可以表示为图,其中顶点表示原子而边表示原子键,他提出了一个刻画分子结构的指数来计算碳原子之间路径的距离,即Wiener指数为碳氢化合物中所有最短碳(碳路径之和),分子的这个简单的数值

在定量结构关系(QSPR/QSAR)中已经被证实是一个很有用的量[2-5],从1947年H.Wiener提出了Wiener指数到目前,各国学者对Wiener指数进行了大量的研究,近年来Wiener指数也被用于通讯网络的研究.

关于Wiener指数的研究已经取得了很大的进展,在文[6]中已经研究了联图Pn∨Pm和Pn∨Cm的Wiener指数. 本文给出笛卡尔积图Pm×Pn的Wiener指数.

1 笛卡尔积图Pm×Pn的Wiener指数

在这一部分,我们首先介绍笛卡尔积图的定义,然后,推出Pm×Pn的Wiener指数.

设G和H是两个图,且V(G)={v1,v2,…,vm},V(H)={u1,u2,…,un},则G和H的笛卡尔积图Pm×Pn定义为V(G×H)=V(G)×V(H)

E(G×H)={(u1,u2);(v1,v2)|u1=v1,u2v2∈E(G)或u2=v2,u1v1∈E(H)}.

如图1所示.

图1 P4×P3

证明对m进行数学归纳法.

1) 当m=1时,W(Pm×P2)=W(P1×P2)=W(P2)=1,结论正确.

2) 假设当m=k时,结论是成立的.即

下面证明当m=k+1时,结论是否成立.

Pk+1×P2就是在Pk×P2上添加两点(u1,vk+1)和(u2,vk+1),并将(u1,vk+1)与(u1,vk),(u2,vk+1)连接,(u2,vk+1)与(u2,vk)连接,如图2所示.

图2 Pk+1×P2

这里距离为1的顶点对增加3对,距离为2,3,4,…,k的顶点对分别增加4对,距离为k+1的顶点增加2对,即(u1,vk+1)和(u2,vk+1)到图Pk+1×P2中所有其他顶点之间的距离之和为

dPk+1×P2(u1,vk+1)+dPk+1×P2(u2,vk+1)=

3+2×4+3×4+…+4k+2(k+1)=2k2+4k+1.

由归纳假设可知

W(Pk+1×P2)=W(Pk×P2)+2k2+4k+1=

故当m=k+1时,结论也成立.

下面我……