辛玉忠， 梁曉東

（新疆大學數(shù)學與系統(tǒng)科學學院，新疆烏魯木齊830046）

一類廣義Sierpin＇ski圖的原子鍵連通度

辛玉忠， 梁曉東?

（新疆大學數(shù)學與系統(tǒng)科學學院，新疆烏魯木齊830046）

Sierpin＇ski圖；廣義Sierpin＇ski圖；ABC指標

拓撲指標在化學，藥理學等方面的研究中發(fā)揮著重要的作用。上世紀中葉以來，研究者們提出了各種各樣的拓撲指標（參見［1，2000］），其中以1975年由MilanRandic′提出的Randic′指標最具代表性［2］。1998年，Estrada等人提出了原子鍵連通度（ABC）指標［3］。一個圖G的原子鍵連通度（ABC）指標定義為：

其中，d（u）表示點u在G中的度數(shù)。ABC指標在化學熱力學及數(shù)學化學中均有廣泛的研究［4］。

定義1 Sierpin＇ski圖S（kn，t）的頂點集是V（S（kn，t））=｛1，2，…，n｝t。｛u，v｝是S（kn，t）的一條邊，當且僅當存在i∈｛1，2，…，t｝使得：

在文獻［9］中，這個結構推廣到了任意圖G，定義為廣義Sierpin＇ski圖，記作S（G，t）。

定義2 廣義Sierpin＇ski圖S（G，t）的頂點集是V（S（G，t））=｛1，2，…，n｝t。｛u，v｝是S（G，t）的一條邊，當且僅當存在i∈｛1，2，…，t｝，使得：

圖1 Sierpin＇ski圖S（K3，3）和廣義Sierpin＇ski圖S（C4，3）

注意到S（G，t）可以由G構造，步驟如下：當t=1時，S（G，1）=G。當t≥2時，首先將S（G，t-1）復制n次，然后在與x相應的那個S（G，t-1）的每個頂點標簽之前添加x，對于G的每一條邊｛x，y｝，在點xyy…y和yxx…x之間添加一條邊。標號為xx…x的點稱為極點。對于任意n階圖G以及任意整數(shù)t≥2，S（G，t）有n個極點。若點x在G中的度數(shù)為d（x），則極點xx…x在S（G，t）中的度數(shù)也為d（x）。S（G，t）中的兩點xyy…y和yxx…x連接S（G，t-1）的兩個拷貝，故它們的度數(shù)分別為d（x）+1和d（y）+1。

圖2 聚合物Sierpin＇ski圖P（K2，3）

用Pn表示階為n的路。在文獻［10，11，2003-2005］中，介紹了構造P（Kn，t）的方法。對于n階連通圖G，文獻［12，2015，145-160］中給出了聚合物Sierpin＇ski圖P（G，t）的如下定義。

定義3 對任意i∈｛1，2，…，t｝，定義集合Ai=｛ai1，ai2，…，aini-1｝。記S（G，i）=（Vi，Ei），其中Vi=｛vi1，vi2，…，vini｝。則廣義Sierpin＇ski圖P（G，t）的點集和邊集分別為：

注意到，P（G，t）可以由如下步驟構造：當t=1時，P（G，1）是由a11連接S（G，1）的一個拷貝的每個頂點構成的。當t=2時，為了得到P（G，2），需要運用P（G，1），A2，S（G，2）；把每一個a2j∈A2與v1j∈V1連接，并且把a2j與G在S（G，2）中的第j個拷貝的所有點連接。相似地，為了得到P（G，t），需要運用P（G，t-1），At，S（G，t）；把每一個atj∈At與vt-1j∈Vt-1連接，并且把atj與G在S（G，t）中的第j個拷貝的所有點連接。

文章中考慮基于廣義Sierpin＇ski圖的網(wǎng)絡模型，獲得了聚合物Sierpin＇ski圖P（G，t）的ABC指標的公式，其中G是一個完全圖或一個無三角形δ正則圖。

1 計算P（G， t）的原子鍵連通度

其中，

證明 令d（x）為點x在P（G， t）中的度數(shù)，對P（G， t）中的邊 ｛x， y｝，分如下情況討論：

（1）x=a1，y∈V1。這種情況下，P（Kn，t）有n條邊 ｛x， y｝，其中d（x）=n，d（y）=n+1，這些邊對ABC指標的貢獻為：

（3）x∈Ai，y∈Vi，2≤i≤t-1。P（Kn，t）有n條邊 ｛x， y｝，其中y是S（Kn，i）的極點，d（x）=d（y）= n+1。同時有ni-n條邊 ｛x， y｝，其中y不是S（Kn，i）的極點，d（x）=n+1，d（y）=n+2。這些邊對ABC指標的貢獻為：

（5）x∈Vi，y∈Ai+1，1≤i≤t-1，P（Kn，t）n條邊 ｛x， y｝，其中x是S（Kn，i）的極點d（x）=d（y）= n+1。同時有ni-n條邊 ｛x， y｝，其中x不是S（Kn，i）的極點，d（x）=n+2，d（y）=n+1。這些邊對ABC指標的貢獻為

（6）x∈At，y∈Vt。P（Kn，t）有n條邊｛x，y｝，其中y是S（Kn，t）的極點，d（x）=n+1，d（y）=n。同時有nt-n條邊｛x，y｝，其中y不是S（Kn，t）的極點，d（x）=d（y）=n+1。這些邊對ABC指標的貢獻為：

推論2 對任意階為n≥2的δ正則圖G，

對給定的圖H，用gH（δ）表示度數(shù)為δ的點的個數(shù)。

引理3［12］對于任意無三角形的n階δ正則圖G以及任意正整數(shù)t≥2，

對給定的圖H，用fH（δ，δ＇）表示兩個頂點度數(shù)分別為δ和δ＇的邊的個數(shù)。

引理4［12］對于任意無三角形的n階δ正則圖G以及任意正整數(shù)t≥2，

定理5 對于任意無三角形的n≥2階δ正則圖G以及任意整數(shù)t≥2，

其中，

證明 令d（x）為點x在P（G，t）中的度數(shù)，｛x， y｝為P（G，t）中的邊。

（1）x=a11，y∈V1。這種情況下，P（G，t）有n條邊 ｛x， y｝，其中d（x）=n，d（y）=δ+2。這些邊對ABC指標的貢獻為：

（2）x，y∈V1。 P（G，t）有條邊 ｛x， y｝，其中d（x）=d（y）=δ+2。這些邊對ABC指標的貢獻為：

d（x）=d（y）=δ+3。 這些邊對ABC指標的貢獻為：

［1］R.Todeschini，V.Consonni.Handbook ofmo1ecu1ar descriptors［J］.Wi1ey-VCH，Weinheim，2000.

［2］M.Randic′.On characterization ofmo1ecu1ar branching［J］.Am.Chem.Soc，1975，（97）：6609-6615.

［3］E.Estrada，L.Torres，L.Rodríguez，I.Gutman.An atom-bond connectivity index：mode11ing the entha1py of formation of a1kanes，Indian［J］. Chem.1998，（37A）：849-855.

［4］E.Estrada，Atom-bond connectivity and the energetic of branched a1kanes［J］.Chemica1Physics Letters，2008，（463）：422-425.

［5］I.Gutman，J.Tosovic＇，S.radenkovic＇，S.Markovic＇，On atom-bond connectivity index and its chemica1app1icabi1ity［J］.Indian Journa1of Chemistry，2012，（51A）：690-694.

［6］A.Graovac，M.Ghorbani，A new version of the atom-bond connectivity index［J］.Acta Chimica S1ovenica，2010，（57）：609-612.

［7］X.Ke，Atom-bond connectivity index of benzenoid systems and f1uoranthene congeners［J］.po1ycyc1ic Aromatic Compounds，2012，（32）：27-35.［8］S.K1avzar，U.Mi1utinovic，Graphs S（n，k）and a variant of the tower of Hanoi prob1em，Czech［J］.Math.J.1997，（47）：95-104.

［9］S.Gravier，M.Kovse，A.Parreau，Genera1ized Sierpin＇ski graphs［J］.Des.Codes Cryptogr.2013（69）：181-188.

［10］A.Jurjiu，Dynamics of po1ymer networksmode1ed by finite regu1ar fracta1s［J］.Ph.thesis.Univ.Freiburg，2005.

［11］A.Jurjiu，T.Kos1owski，A.B1umen，Dynamics of deterministic fracta1po1ymer networks：hydrodynamic interactions and the absence of sca1ing［J］. Chem.Phys.，2003，（118）：2398.

［12］Juan A.Rodriguez-Veazquez，Jessica Toma＇s-Andreu.On the randic′index of po1ymeric networksmode11ed by genera1ized Sierpin＇ski graphs，MATCH Commun［J］.Math.Comput.Chem，2015，（74）：145-160.

Atom-bond Connectivity Index of Generalized Sierpin＇ski Graph

XlNYu-zhong， LlANG Xiao-dong?
（School ofMathematics and System Sciences，Xinjiang University，Urumqi，Xinjiang，830046，China）

Sierpin＇ski graph；Genera1ized Sierpin＇ski graph；ABC index

O157.5

A

1008-9659（2015）04-031-07

2015-09-17

新疆維吾爾自治區(qū)重點實驗室開放課題資助（2015KL019）。

辛玉忠（1991-），男，青海人，碩士研究生，主要從事圖與網(wǎng)絡優(yōu)化方面的研究。

?［通訊作者］梁曉東（1970-），男，副教授，博士，碩士生導師，主要從事圖與網(wǎng)絡優(yōu)化方面的研究。