乘積圖的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.