乘积图的Hyper-Wiener 指标

陈育栎

(福州大学至诚学院 计算机工程系，福州 福建350002)

在化学理论中，分子的化学和物理性能一般可用分子图的拓扑指标反映出来，而不同的分子拓扑指标反映出该分子的不同性能，所以在化学界出现了很多种重要的分子拓扑指标。基于分子图的顶点间距离的拓扑指标对刻画分子图以及建立分子结构和特征间的关系有重要作用，同时被广泛用于预测化合物的物理化学性质和生物活性，因此具有重要的理论价值和应用背景。Wiener 指标是研究最为广泛的拓扑指标之一，它是Wiener 于1947 年考察烷烃的沸点与分子结构的关系时最先提出的。在Wiener 指标的基础之上，1993 年Randi＇c 提出了无圈图的hyper-Wiener 指标的定义。

关于图的Wiener 指标和hyper-Wiener 指标的数学性质和化学应用见文献［1-6］。有关连通图的Wiener 指标和hyper-Wiener 指标的研究已经有很多好的结果，但对两个图的乘积图的hyper-Wiener指标的研究相对较少，文中主要研究乘积图的hyper-Wiener 指标的性质，并给出直积图的hyper-Wiener 指标的计算公式。

1 乘积图的介绍

图的直积是一种直观且自然的构建，曾经得到广泛研究和探讨。直积具有大量的代数性质，也被认为是图与图的所有乘积运算中最简单的一种。两个图G 和H 的直积G × H 定义如下:

定义1 G × H 点集为

边集为

根据直积图的定义，容易得到直积图中顶点的个数为

边的个数为

定义2 字典序积图G［H］的点集为

边集为

根据字典序积图的定义可以观察到:字典序积G［H］可以看作将图G 的每个顶点(如u1，u2)替换成图H 的拷贝Hu1Hu2，点集Hu1中所有点与Hu2中的所有点当u1u2∈E(G)时相邻。定义3 联接图G + H 的点集为

边集为联接点集V(G)与V(H)中顶点的边的集合(即每条边的两个端点一个是G 中的点，另一个是H中的点)。

定义4 分离图G ∨H 的点集为

边集为

Fath-Tabar 和Ashrafi［7］通过上述所定义的乘积图点和边之间的关系，刻画出以上乘积图中任意两点间的距离:

1)如果G 是| V(G)| ＞1 的连通图，那么对字典序积图G［H］中的任意两点(u1，v1)，(u2，v2)，根据定义得到其间的距离关系，具体刻画如下:

2)联接图G + H 中的任意两点u，v 间的距离:

3)分离图G ∨H 的中任意两点(a，b)，(c，d)间的距离:

通过刻画以上乘积图中点与点的距离规律，Fath-Tabar 和Ashrafi［7］得到了以上几类乘积图的hyper-Wiener 指标。受到该思想启发，文中研究任意两个连通图的直积图的hyper-Wiener 指标性质，并给出直积图的hyper-Wiener 指标的计算公式。

2 主要结果

根据定义1，观察直积图(也称为笛卡尔乘积图)的结构可以得到以下性质:

性质1 如果(a，b)，(x，y)是乘积图G × H 的两个点，那么其间的距离如下:

由以上直积图中两点之间的距离关系可以得到文中的主要结论。

引理1 设Pm和Pn是顶点数分别为| V(Pm)| =m，| V(Pn)| = n 的路图，则有:

证 路与路的直积图Pm× Pn，设Pm= xi1xi2…xim，Pn= xj1xj2…xjn，由Pm和Pn的直积图Pm× Pn的定义得到图上任意两点间的距离应满足下面的关系式:

结合hyper-Wiener 指标的定义可以得到:

证毕。

现在考虑圈和路的直积图Cm×Pn，同理可以证明下面的结果:

定理1 设Cm和Pn分别是点数| V(Cm)| = m，| V(Pn)| =n 的圈和路图，则有:

证 现考虑圈与路的直积图Cm× Pn，由直积图的结构考虑其中点同样存在性质1 中刻画的距离关系，则利用引理1 同样的做法，也可以得到类似结论:

最后，考虑将结论推广到任意两个图G 和H 的直积图G × H，根据其图中任意两点距离的关系和hyper-Wiener 指标的定义可以得到:

定理2 设G 和H 是顶点数分别为| V(G)| = m，| V(H)| =n 的连通图，则有:

证 由性质1 G 和H 的乘积图G ×H 的结构得到图上任意两点间距离满足下面的关系式:

由此可见，其具有引理1 中路与路的直积图的类似结构性质，所以考虑将引理1 的结论推广到任意两个图G 和H 的直积图G ×H。根据上述直积图任意两点距离的关系和hyper-Wiener 指标的定义可以得到

证毕。

这样，就可以通过已经研究出的图类(如路图，树图，单圈图，双圈图)的Wiener 指标，和hyper-Wiener 指标［8］计算其乘积图的hyper-Wiener 指标。

［1］Cash G G.Polynomial expressions for the hyper-Wiener index of extended hydrocarbon networks［J］. Comput Chem，2001，25:577-582.

［2］Wiener H.Structural determination of paraffin boiling points［J］.J Amer Chem Soc，1947，69:17-20.

［3］DENG H. On the extremal Wiener polarity index of chemical trees［J］. MATCH Commun Math Comput Chem，2011，66:305-314.

［4］Klein D J，Lukovits I.On the definition of the hyper-Wiener index for cycle-containing structures［J］.J Chem Inf Comput Sci，1995，35:50-52.

［5］Gutman I.Relation between hyper-Wiener and Wiener index［J］.Chem Phys Lett，2002，364:352-356.

［6］ZHOU Bo，Gutman I.Relations between Wiener，hyper-Wiener and Zagreb indices［J］.Chem Phys Lett，2004，394:93-95.

［7］Fath-Tabar G H，Ashrafi A R. The hyper-Wiener polynomial of graphs［J］. Iranian Journal of Mathematical Sciences and Informatics，2011，6(2):67-74.

［8］XING Rundan，ZHOU Bo，QI Xuli.Hyper-Wiener index of unicyclic graphs［J］.MATCH Commun Math Comput Chem，2011，66:315-328.