兩類(lèi)運(yùn)算圖的Merrifield-Simmons指標(biāo)

陳妹君，田雙亮

(西北民族大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，甘肅 蘭州 730030)

Merrifield-Simmons 拓?fù)渲笜?biāo)是化學(xué)分子圖論研究中比較流行和重要的拓?fù)渲笜?biāo)之一，最早是由美國(guó)化學(xué)家Richard E Merrifield 和Howard E Simmons 在文獻(xiàn)［1］中應(yīng)用有限拓?fù)潢U述化學(xué)分子結(jié)構(gòu)理論時(shí)提出的.在此基礎(chǔ)上，文獻(xiàn)［2］對(duì)該指標(biāo)做了進(jìn)一步研究，并驗(yàn)證了這個(gè)有限拓?fù)涞拈_(kāi)集數(shù)等于點(diǎn)獨(dú)立集數(shù)，并用符號(hào)σ 表示.但這個(gè)指標(biāo)的名稱(chēng)一直沒(méi)有確定下來(lái)，直到Gutman 在文獻(xiàn)［3］中第一次用Merrifield -Simmons 來(lái)命名這個(gè)拓?fù)渲笜?biāo)，并且得到了認(rèn)可.有關(guān)Merrifield-Simmons 指標(biāo)的應(yīng)用及最新的研究成果在參考文獻(xiàn)［4-6］中有詳細(xì)闡述.本文討論廣義字典積P3［Pm］(如圖1)與P3［Cm］(如圖2)的Merrifield-Simmons 指標(biāo)，并給出一種計(jì)算公式.

圖1 廣義字典積P3［Pm］

圖2 廣義字典積P3［Cm］

1 基本概念和引理

文中所考慮的圖G 都是有限無(wú)向的簡(jiǎn)單圖.用V(G)、E(G)分別表示圖G 的頂點(diǎn)集與邊集.

定義1［7］設(shè)G 是具有頂點(diǎn)集V(G)= {t0，t1，…，tn－1}(n ≥2)的圖，hn= (Hi)i={0，1，…，n－1}是不相交圖的序列，其中Hi的頂點(diǎn)集為V(Hi)={(ti，y1)，…，(ti，yx)}，x ≥1．稱(chēng)G［hn］為G 與hn= (Hi)i={0，1，…，n－1}的廣義字典積，其中G［hn］的頂點(diǎn)集為，且兩個(gè)頂點(diǎn)(ti，yp)與(tj，yq)相鄰當(dāng)且僅當(dāng)ti= tj且(ti，yp)(tj，yq)∈E(Hi)，或(ti，tj)∈E(G).若Hi?H，i= 0，1，…，n－1 ，則將G［hn］記為G［H］且稱(chēng)G［H］為G 與H 的字典積.

定義2［8］設(shè)G 是一個(gè)圖，v 是圖G 的任意一個(gè)頂點(diǎn)，則稱(chēng)

是v 的相鄰頂點(diǎn)集，稱(chēng)

是v 的閉鄰集.

引理1［8］設(shè)G 是一個(gè)圖，對(duì)圖G 的任意一個(gè)頂點(diǎn)v，則有

σ(G)= σ(G － u)+ σ(G － NG［u］).

引理2［8］若G1，G2，…，Gt是圖G 的連通分支，則有

設(shè)Fn是Fibonacci 數(shù)，其定義為F0= 0，F(xiàn)1=1，n ≥2 時(shí)，F(xiàn)n= Fn－1+ Fn－2，則有以下引理:

引理3［8］設(shè)Pn為n 階的路，則有

引理4［8］設(shè)Cn為n 階的圈，則有

2 主要結(jié)論及證明

定理1 當(dāng)m ≥4 時(shí)，

證明 對(duì)m 用數(shù)學(xué)歸納法.

1)當(dāng)m = 4 時(shí)，P3［Pm］= P3［P4］，如圖3所示.

圖3 P3［P4］

結(jié)論成立.

2)假設(shè)當(dāng)m = k －1 時(shí)，有

3)當(dāng)m = k 時(shí)，

綜上所述，當(dāng)m ≥4 時(shí)，有

定理2 當(dāng)m ≥4 時(shí)，

證明 由引理1 和定理1 可知:

［1］Merrifield R E，Simmons H E.The structures of mole cular topological spaces［J］.Theoretica Chimica Acta，1980，55(1):55 -75.

［2］Merrifield R E，Simmons H E.Topological methods in chemistry［M］.New York:Wiley，1989.

［3］Gutman I.Fragmentation formulas for the number of Kekulé structures，Hosoya and Merrifield - Simmons indices and related graph invariants［J］.Coll.Sci.Pap.Fac.Sci.Kragujevac，1990(11):11 -18.

［4］Trinajstic N.Chemical graph theory［M］.Boca Rator，F(xiàn)L:CRC Press，1992.

［5］Deng H Y.The smallest Merrifield -Simmons index of(n，n + 1)- graphs［J］.Mathematical and Computer Modeling，2009，49(1 -2):320 -326.

［6］Xu K X.On the Hosoya index and the Merrifield -Simmons index of graphs with a given clique number［J］.Applied Mathematics Letters，2010，23(4):395-398.

［7］Waldemar S，Iwona W，Andrej W.On the existence and on the number of(k，l)- kernels in the lexicographic product of graphs［J］.Discrete Mathematics，2008，308:4616 -4624.

［8］Gutman I，Polansky O E.Mathematical concepts in organic chemistry［M］.Berlin:Springer，1986.