路與圈的笛卡爾積的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所示。由圖2和定義2可知，求頂點vij到其他頂點的距離之和可以轉化為求頂點vij到4個部分中所有的頂點的距離之和，此時注意到在計算過程中，第i行和第j列的頂點分別計算了兩次。

圖2 Pn×Pm

在圖H1中，它是由行為i個頂點、列為j個頂點構成的笛卡爾積圖，記作Pi×Pj，根據圖的Wiener指數的對稱性，點vij到H1所有頂點的距離之和等于v11到H1所有頂點的距離之和，即dH1(v11)=dH1(vij)，根據引理1可知：

同理可得

在圖Pn×Pm中，第i行和第j列上的所有點到點vij的距離記為d′(vij)，則有：

即在圖Pn×Pm中，點vij到其他所有頂點的距離之和為

下面用相同的方法證明Cn×Pm的Wiener 指數。

引理2（1）對于圖C2k×Pm，有

（2）對于圖C2k+1×Pm，有

證明在圖C2k×Pm中，將第i行第1 列的頂點記為vi1，根據圈的Wiener指數的性質，任意一點到其他頂點的距離之和都相同。則頂點vi1的Wiener指數與頂點v11的Wiener指數相等，有：

僅對（1）進行證明，對（2）同理。

則對于任意圖C2k+1×Pm，頂點vi1的Wiener 指數為：

定理3設n，m為正整數，則

證明由定理1 可知，圈的Wiener 指數與圈的頂點個數的奇偶性有關，所以需要對圈Cn進行分類討論，由于n=2k和n=2k+1 的證明方法是一樣的，因此接下來只給出n=2k的證明。

當n=2k時，將圖C2k×Pm記作圖H′，由引理2可得，第i行第1 列的點vi1的Wiener 指數為d（H′vi1)=mk2+m2k-mk。

任取第j列，以第j列為界，將圖H′分為2 個部分，分別記作H′1、H′2，如圖3所示。

圖3 C2k×Pm

根據圖的Wiener的對稱性，可得：

由定理1可知，點vij在圈中的Wiener指數為：d″(vij)=k2，所以

同理，當n=2k+1可得

3 結語

本文主要通過路的Wiener指數的對稱性，對路與路的笛卡爾積圖和圈與路的笛卡爾積圖進行分塊，對每一塊所得結果通過求和計算得到了它們的Wiener 指數。在此方法和結論的基礎上，后續將會對其他特殊圖（如星圖）和路笛卡爾積的Wiener 指數進行研究。此類方法也為進一步研究其他特殊圖的Wiener指數提供參考。