路的笛卡尔积图的Wiener指数

于 玲， 叶永升

(淮北师范大学 数学科学学院,安徽 淮北 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时,结论也成立.

下面我们给出笛卡尔积图Pm×Pn的Wiener指数.

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

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

W(Pm×Pk)=3m-2+2(4m-6)+3[2+(4m-3)]+

4[2+4(m-4)]+…+6(m+1)+2m+(k-2)(2m-1)+

2(k-2)[2(m-1)+m-2]+3[2(k-2)(m-1)+2(k-1)(m-2)]+

4[2(k-3)(m-1)+2(k-2)(m-2)+2(k-2)(m-3)]+

5[2(k-4)(m-1)+2(k-3)(m-2)+2(k-2)(m-3)+

2(k-2)(m-4)]+…+(m-2)[2(k-m+3)(m-1)+2(k-m+2)(m-2)+…+

2×3(k-3)+2×2(k-2)+2(k-2)]+3(k-2)(m-3)+

4(k-2)(m-4)+…+2(m-2)(k-2)+2m(k-2)+3m(k-3)+…+m(k-1)+

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

图Pm×Pk+1就是在图Pm×Pk上添加点(uk+1,v1),(uk+1,v2),(uk+1,v3),…,(uk+1,vm),并将(uk+1,v1)与(uk,v1),(uk+1,v2)连接,(uk+1,v2)与(uk,v2)和(uk+1,v3)连接,(uk+1,v3)与(uk,v3)和(uk+1,v4)连接,…,(uk+1,vm-1)与(uk,vm-1)和(uk+1,vm)连接,如图3所示.

图3 Pm×Pk+1

dPm×Pk+1(uk+1,v1)+dPm×Pk+1(uk+1,v2)+dPm×Pk+1(uk+1,v3)+…+dPm×Pk+1(uk+1,vm)=

2m-1+2[2(m-1)+m-2]+3[2(m-1)+2(m-2)]+4[2(m-1)+

2(m-2)+2(m-3)]+…+(m-2)[2(m-1)+2(m-2)+2(m-2)+…2×2+2]+

(m-1)[8(k-2)+2(k-3)+2(k-4)+…+2]+

m[7k-12+2+3+4+…k-1+2+4+6+…+2(k-3)]+

(m+1)[(k-1)+(k-2)+(k-3)+…+1]+(m+2)[(k-2)+(k-3)+…+1]+…+

10(m+k-4)+6(m+k-3)+3(m+k-2)+m+k-1=

由归纳假设可知

W(Pm×Pk+1)=W(Pm×Pk)+dPm×Pk+1(uk+1,v1)+dPm×Pk+1(uk+1,v2)+…+dPm×Pk+1(uk+1,vm)=

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

[1]Wiener H.Structural determination olf paraffin boiling points[J]. J Amer Chen Soc,1947,69:17-20.

[2]Rouveray D H.Predictinging chemistry from topology[J]. Sci Amer,1986,255(9):40-47.

[3]Devillers J.Topological Indices and Related Descripotors in QSAR and QSPR[M]. Bostons:Kluwer Acacdemic publishers,1999.

[4]Gutman I,Potgieter J H.Wiener index and intermolecular forces[J].J Serb Chem Soc,1997,62:185-192.

[5]Nikklic S,Trinajsti N C,Mihali Z C.The Wiener index:developments and applications[J].Groat Chem Acta,1995,68:105-129.

[6]于玲,叶永升.路与圈的联图的Wiener指数[J].淮北师范大学学报：自然科学版,2011,32(1):1-3.

[7]Dobrymin A A,Entriger R,Gutman I. Wiener index of trees:theory and applications[J].Acta Appl Math,2001,66::211-249.

[责任编辑：李春红]

TheWienerIndicesofCartesianproductPm×Pn

YU Ling， YE Yong-sheng

(School of Mathematical Science,Huaibei normal University,Huaibei Anhui,235000,China)

distance; cartesian product; wiener index

O157.5

A

1671-6876(2012)01-0013-04

2011-10-07

国家自然科学基金资助项目(10301010)

于玲(1986-),女,江苏镇江人,硕士研究生,研究方向为图论及其应用.