Cluster與Corona乘積圖的hyper-Wiener指標(biāo)

羅朝陽孫德榮蔡 華

（1，2，3.昌吉學(xué)院數(shù)學(xué)系 新疆 昌吉 831100）

Cluster與Corona乘積圖的hyper-Wiener指標(biāo)

羅朝陽1孫德榮2蔡 華3

（1，2，3.昌吉學(xué)院數(shù)學(xué)系 新疆 昌吉 831100）

分別給出了兩個連通圖G和H的Cluster與Corona乘積G{H}和G。H的hyper-Wiener指標(biāo)的精確表達式及其應(yīng)用例子.

Hyper-Wiener指標(biāo),Cluster乘積,Corona乘積,連通圖

1 引言

分子結(jié)構(gòu)描述符Top又稱分子拓?fù)渲笜?biāo)．它是一個與化學(xué)分子圖相關(guān)的實常數(shù)且不依賴于該分子圖的標(biāo)記和結(jié)構(gòu)性特征表示.迄今為止，大量的分子拓?fù)渲笜?biāo)，如第一、二類Zagreb指標(biāo)M1和M2，Wiener指標(biāo)W，hyper-Wiener指標(biāo)WW，Randic'指標(biāo)R，Hosoya指標(biāo)Z，Szeged指標(biāo)Sz和點、邊PI指標(biāo)PIv和PIe以及它們的改進版和變體等，已經(jīng)在許多化學(xué)類研究文獻中被定義，這些拓?fù)渲笜?biāo)的許多數(shù)學(xué)性質(zhì)也在數(shù)學(xué)類文獻中被研究。同時發(fā)現(xiàn)那些基于圖中點度和距離的拓?fù)渲笜?biāo)在物理化學(xué)建模、藥理學(xué)、毒理學(xué)、生物學(xué)和納米材料學(xué)、化合物的其它性質(zhì)的研究以及QSPR和QSAR分析中分子螺旋形態(tài)的表征等方面都有重要的應(yīng)用．

1947年,美國化學(xué)家Wiener［1］為了研究石蠟的沸點，提出了基于圖中距離的拓?fù)渲笜?biāo)—Wiener指標(biāo)，該指標(biāo)之后便得到廣泛地關(guān)注和研究。連通圖G的Wiener指標(biāo)被定義為G中所有無序點對之間距離的和.研究顯示該指標(biāo)與分子的物理化學(xué)性質(zhì)具有高相關(guān)性．關(guān)于Wiener指標(biāo)的更多研究結(jié)果與應(yīng)用,見文獻［2–8］.無圈圖的hyper-Wiener指標(biāo)首先是由Milan Randic'在1993年提出的,之后Klein［9］等人將此定義推廣到所有連通圖.Khalifeh等人［10］計算了圖的笛卡爾乘積，復(fù)合，連圖和不交并的hyper-Wiener指標(biāo).Metsidik等人［11］確定了F-sum圖的hyper-Wiener指標(biāo).Eliasi和Iranmanesh［12］計算了廣義層積圖的hyper-Wiener指標(biāo).關(guān)于hyper-Wiener指標(biāo)的若干化學(xué)應(yīng)用和數(shù)學(xué)性質(zhì)見文獻［13–18］.

近十年間,由于大分子合成的需要以及超大型復(fù)雜網(wǎng)絡(luò)的出現(xiàn),對于合成圖的研究屢見不鮮.特別是乘積圖（笛卡爾積、克羅內(nèi)克積、Cluster積、Corona積、層積及廣義層積等）,復(fù)合圖,連圖,圖的對稱差、不交并等的相應(yīng)拓?fù)渲笜?biāo)的研究成果居多.Yeh和Gutman計算了一些合成圖的Wiener指標(biāo).Sagan等人［19］及Stevanovic'［20］確定了一些合成圖的Hosoya多項式.張和平等人［21］計算了連圖，Cluster乘積圖和Corona乘積圖的Kirchhoff指標(biāo).本文給出了連通圖G和H的Cluster乘積和Corona乘積G{H}和G°H的hyper-Wiener指標(biāo)的精確表達式，同時利用所得結(jié)果計算了一些特殊圖類的Cluster和Corona乘積圖的hyper-Wiener指標(biāo).

2 預(yù)備知識

文中涉及的圖均為有限的無向簡單連通圖,未定義的術(shù)語與符號見文［22］.設(shè)連通圖G的點、邊集分別為V（G）和E（G）,它們的基數(shù)記為|G|和|E（G）|.圖G中點v的度及點v的鄰點集合分別記為dG(v)和

NG(v),則dG(v)=|NG(v)|.圖G中任意兩點u和v之間的距離dG(u,v)表示u和v間的一條最短路的邊數(shù).令d(u,G)=∑v∈V(G)dG(u,v)且d'(u,G)=∑v∈V(G)(dG(u,v))2.對于圖G和H，若存在雙射θ:V（G）→V（H）與φ:E（G）→E（H），使得ΨG(e)=uv當(dāng)且僅當(dāng)ΨG(φ(e))=θ(u)θ(v)，則稱G和H同構(gòu),記為G?H.一般地,若G?H,則Top（G）=Top（H）.

連通圖G的Wiener指標(biāo)W(G)和hyper-Wiener指標(biāo)WW(G)分別定義如下：

一個根圖是指選定它的一個點作為根點，以區(qū)別于其余點.本文主要涉及的幾種合成圖為：Cluster乘積圖，Corona乘積圖和連圖［8］.

連通圖G和H（根圖）的Cluster乘積記為G{H}，由G的一個拷貝和根圖H的|G|個拷貝構(gòu)成，是將H的第i個拷貝的根點與G的第i個點相連，i=1,2,···,|G|.

連通圖G和任意一個圖H的Corona乘積記為G°H，由G的一個拷貝和H的|G|個拷貝構(gòu)成，是將H的第i個拷貝的每一個點都與G的第i個點相連，i=1,2,···,|G|.

圖G和H連圖G+H：V（G+H）=V（G）∪V（H）；E（G+H）=E（G）∪E（H）∪{（u,v）|u∈V（G）,v∈V（H）}.

關(guān)于兩個圖的Cluster與Corona乘積的Wiener指標(biāo)，有如下已知結(jié)果：

定理1.［8］設(shè)G和H為連通圖,x是圖H的根點，則

定理2.［8］設(shè)G為連通圖，則對于任意圖H，有

3 Cluter乘積圖的hyper-Wiener指標(biāo)

設(shè)G和H為兩個連通圖,Hi（i=1,2,···,|G|）是H的第i個拷貝.簡便起見，記u∈V(Hi)為u∈Hi.下面給出Cluster乘積圖G{H}的hyper-Wiener指標(biāo)的計算表達式.

定理3.設(shè)圖G和H連通，x是H的根點,則

證明.先求W2（G{H}）.若G{H}的點u和v均屬于H的同一拷貝,則dG{H}(u,v)=dH(u,v).這些點對給W2（G{H}）的貢獻為=|G|W2（H）.若G{H}的點u和v分別屬于H的不同拷貝，則dG{H}(u,v)=dH(u,xi)+dG(xi,xj)+dH(xj,v)，其中xi和xj分別是G的被H的根點粘附的兩個點.i,j∈{1,2,…, |G|}且i≠j.這些點對給W2（G{H}）的總貢獻為

對以上兩類G{H}的無序點對u,v的貢獻求和，得

根據(jù)hyper-Wiener指標(biāo)的定義，由等式（3）和（5）可得,

證畢.

引理1.［10,19］設(shè)Kn、Pn和Cn分別表示n階完全圖、路和圈,其中x為它們的根點.Kn與Cn中點x任選，Pn中點x取其一個懸掛點.則

例1.設(shè)m,n為正整數(shù)且m≥2,n≥2.令x為Kn與Pn的根點.Kn中x任選，Pn中x為其一個懸掛點.則由定理3和引理1,可得

同理可計算Pm{Ck}，Cm{Ck}和Ck{Pn}（k=2n,2n+1）等Cluster乘積圖的hyper-Wiener指標(biāo).由于計算方法類似，故此處略去相應(yīng)的表達式.

4 Corona乘積圖的hyper-Wiener指標(biāo)

下面計算G和H的Corona乘積G。H的hyper-Wiener指標(biāo).關(guān)于任意兩個圖的連圖的hyper-Wiener指標(biāo)，有以下已知結(jié)果：

定理4.［10］對于任意兩個圖G和H，有

由于兩個圖join運算滿足交換律，令G?K1，x為K1中的唯一孤立點，則H+x?H+K1.故引理2是定理4的直接結(jié)果.

引理2.對于圖H和任意一個孤立點x，有

定理5.設(shè)圖G連通,則對于任意圖H,有

證明.令x為圖H+x的根點.因為G°H?G{H+x}，于是由定理3和引理2，定理5得證.

例2.設(shè)m,n為正整數(shù)且m≥2，n≥2.則由引理1和定理5，得

類似地，可計算Pm°C2n+1，C2m°C2n，C2m+1°C2n+1及C2m+1°C2n等的hyper-Wiener指標(biāo)，此處略去。

［1］Wiener H.Structural determination of paraffin boiling points［J］.Journal of the American Chemical Society,1947,69:17-20.

［2］Gutman I,Polansky O E.Mathematical Concepts in Organic Chemistry［M］.Berlin:Springer, 1986.

［3］Dobrynin A A,Entringer R,Gutman I.Wiener index of trees:Theory and applications［J］.Acta Appl.Math.,2001,66:211-249.

［4］Dobrynin A A,Gutman I,Klav?ar S,ZigertP.Wiener index of hexagonal systems［J］.Acta Appl. Math.,2002,72:247-294.

［5］Gutman I,Klavoar S,Mohar B.（Eds.）Fifty years of the Wiener index［J］.MATCH Commun. Math.Comput.,1997,35:1259.

［6］Graovac A,Pisanski T.On the Wiener index of a graph［J］.J.Math.Chem.,1991,8:53-62.

［7］Klav?ar S,Gutman I.Wiener number of vertex-weighted graphs and a chemical application［J］. Discrete Appl.Math.,1997,80:73-81.

［8］Yeh Y N,Gutman I.On the sum of all distances in composite graphs［J］.Discrete Math.,1994, 135:359-365.

［9］Klein D J,Lukovits I,Gutman I.On the definition of the hyper-Wiener index for cyclecontaining structures［J］.J.Chem.Inf.Comput.Sci.,1995,35:50-52.

［10］Khalifeh M H,Yousefi-Azari H,Ashrafi A R.The hyper-Wiener index of graph operations［J］. Comput.Math.Appl.,2008,56:1402-1407.

［11］Metsidik M,Zhang W,Duan F.Hyper-and reverse-Wiener indices of F-sums of graphs［J］.Discrete Appl.Math.,2010,158:1433-1440.

［12］Eliasi M,Iranmanesh A.The hyper-Wiener index of the generalized hierarchical product of graphs［J］.Discrete Appl.Math.,2011,159:866-871.

［13］Cash G G.Relationship between Hosaya polynomial and the hyper-Wiener index［J］.Appl. Math.Lett.,2002,15:893-895.

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

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

［16］Klav?ar S,Gutman I.A theorem on Wiener-type invariants for isometric subgraphs of hypercubes［J］.Appl.Math.Lett.,2006,19:1129-1133.

［17］Klav?ar S,Zigert P,Gutman I.Analgorithm for the calculation of the hyper-Wiener index of benzenoid hydrocarbons［J］.Comput.Chem.,2000,24:229-233.

［18］Pattabiraman K,Paulraja P.On some topological indices of the tensor products of graphs［J］.Discrete Appl.Math.,2012,160:267-279.

［19］Sagan B Y,Yeh Y N,Zhang P.The wiener polynomial of a graph［J］.Int.J.Quantum Chem., 1996,60:959-969.

［20］Stevanovi[c']D.Hosoya polynomial of composite graphs［J］.Discrete Math.,2001,235（1）:237-244.

［21］Zhang H P,Yang Y J,Li C W.Kirchhoff index of composite graphs［J］.Discrete Appl.Math., 2009,157:2918-2927.

［22］West D B.Introduction to Graph Theory,second ed［M］.NJ:Prentice-Hall,Upper Saddle River,2001.

O157.5,O157.6

：A

：1671-6469（2013）04-0072-05

2013-07-03

昌吉學(xué)院科研基金項目（2012YJYB003）

羅朝陽（1969-），男，陜西禮泉人，昌吉學(xué)院數(shù)學(xué)系，副教授，研究方向：復(fù)雜網(wǎng)絡(luò)，圖論及其應(yīng)用。