劉睿琳，田雙亮，田文文

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

?

一類多圈圖關(guān)于Merrifield-Simmons指標(biāo)的計(jì)數(shù)

劉睿琳，田雙亮，田文文

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

圖G的Merrifield-Simmons指標(biāo)表示該圖中所有獨(dú)立集的數(shù)目。主要研究了一類多圈圖Gm(n)關(guān)于Merrifield-Simmons指標(biāo)的計(jì)數(shù)問題，并給出了具體的表達(dá)式。

多圈圖；Merrifield-Simmons指標(biāo)；計(jì)數(shù)

0 引言

自1989年美國化學(xué)家Merrifield和Simmons在文獻(xiàn)[1]中提出Merrifield-Simmons指標(biāo)之后，由于這一化學(xué)拓?fù)渲笜?biāo)與物質(zhì)的沸點(diǎn)有著密切的關(guān)系，且有著相當(dāng)廣泛的應(yīng)用，參見文獻(xiàn)[2,3]。隨后，國內(nèi)外很多學(xué)者對此進(jìn)行了大量的研究工作，文獻(xiàn)[4]中關(guān)于最大和最小的Merrifield-Simmons指標(biāo)和Hosoya指標(biāo)給出了一個很好的綜述，并提出了一些有待解決的公開問題。文獻(xiàn)[5]中研究了兩類多元素鏈在不同構(gòu)聯(lián)接位下的Merrifield-Simmons指標(biāo)的計(jì)數(shù)問題。文獻(xiàn)[6]中研究了一類(n，n+2)-圖關(guān)于兩種拓?fù)渲笜?biāo)的排序。本文研究了一類多圈圖Gm(n)關(guān)于Merrifield-Simmons指標(biāo)的計(jì)數(shù)問題，并給出了具體的表達(dá)式。文中未加說明的符號及術(shù)語參見文獻(xiàn)[7]。

本文研究的多圈圖Gm(n)是由n個m階圈Cm(1),Cm(2),…,Cm(n)構(gòu)成的圈序列，其中滿足相鄰兩個圈之間只有一個公共頂點(diǎn)。

不妨設(shè)V(Cm(i))∩V(Cm(i+1))={ui},i=1,2,…,n，Cm(n+1)=Cm(1)，且d(ui,ui+1)=k，如圖1所示。

圖1 多圈圖Gm(n)Fig.1 some-cycle graphGm(n)

在證明主要結(jié)論之前，先給出幾個相關(guān)引理如下。

引理1[2]設(shè)G是一個簡單的連通圖，對任意的u，v∈V(G)，uv∈E(G)，則有(i)σ(G)=σ(G-v)+σ(G-NG[v])；(ii)σ(G)=σ(G-uv)-σ(G-(NG[u]∪NG[v]))。

引理3[2]對于n階的路Pn，有σ(Pn)=fn+2。

1 主要結(jié)論及其證明

引理4 對于如圖2所示的圖H，其Merrifield-Simmons指標(biāo)為：

圖2 圖HFig.2 graphH

證 由引理1-3可得

σ(H)=σ(H-u)+σ(H-NH[u])

=fs+2ft+2fp+2fq+2+fs+1ft+1fp+1fq+1

從而引理4得證。

引理5 對于如圖3所示的圖Hm(1)，其Merrifield-Simmons指標(biāo)為：

σ(Hm(1))=(fs+2ft+2fs+1ft+1)

圖3 圖Hm(1)Fig.3 graphHm(1)

證 由引理1-4可得

σ(Hm(1))=σ(Hm(1)-u1)+σ(Hm(1)-NHm(1)[u1])

=fp+2fq+2·(fs+2ft+2fm-k+1fk+1+fs+1ft+1fm-kfk)+

fp+1fq+1·(fs+2ft+2fm-kfk+fs+1ft+1fm-k-1fk-1)

從而引理5得證。

定理1 對于如圖4所示的圖Hm(n)，其Merrifield-Simmons指標(biāo)為：

σ(Hm(n))=(fs+2ft+2fs+1ft+1)

圖4 圖Hm(n)Fig.4 graphHm(n)

證 由數(shù)學(xué)歸納法可知

當(dāng)n=1時，由引理5可知結(jié)論成立。

假設(shè)當(dāng)n=r時結(jié)論成立，即

σ(Hm(r))=(fs+2ft+2fs+1ft+1)

則當(dāng)n=r+1時，有

σ(Hm(r+1))=σ(Hm(r+1)-ur+1)+σ(Hm(r+1)-NHm(r+1)[ur+1])

=fp+2fq+2·(fs+2ft+2fs+1ft+1)

fp+1fq+1·(fs+2ft+2fs+1ft+1)

令p=m-k-1，q=k-1，則有

σ(Hm(r+1))=(fs+2ft+2fs+1ft+1)

即當(dāng)n=r+1時，結(jié)論亦成立。

故σ(Hm(n))=(fs+2ft+2fs+1ft+1)

定理2 對于多圈圖Gm(n)，其Merrifield-Simmons指標(biāo)為：

σ(Gm(n))=(fm-k+1fk+1fm-kfk)

證 由引理1及定理1可知

σ(Gm(n))=σ(Gm(n)-un)+σ(Gm(n)-NGm(n)[un])

從而定理2得證。

[1]MERRIFIELDRE，SIMMONSHE．TopologicalMethodsinChemistry[M]．NewYork：Wiley，1989．

[2]GUTMANI，POLANSKYOE．MathematicalConceptsinOrganicChemistry[M]．Berlin：Sprin-ger，1986．

[3]GUTMANI，CYVINSJ．IntroductiontotheTheoryofBenzenoidHydrocarbons[M]．Berlin：Springer，1989．

[4]WAGNERS，GUTMANI．MaximaandminimaoftheHosoyaIndexandtheMerrifield-Simmonsindex[J]．ActaApplMath,2010，112：323-346．

[5] 田雙亮，田文文，王倩，等．多元素鏈的Merrifield-Simmons指標(biāo)和Hosoya指標(biāo)[J]．山西大學(xué)學(xué)報(自然科學(xué)版)，2014，37(1)：48-52．

[6] 田文文，田雙亮，王燕鳳．一類(n,n+2)-圖關(guān)于兩種拓?fù)渲笜?biāo)的排序[J]．貴州師范大學(xué)學(xué)報(自然科學(xué)版)，2015，33(6)：53-56．

[7]BONDYJA，MURTYUSR．Graphtheorywithapplications[M]．NewYork：Macmillan，1976．

The number of a class of some-cycle graph with respect to Merrifield-Simmons index

LIU Ruilin，TIAN Shuangliang，TIAN Wenwen

(School of Mathematics and Computer Science，Northwest University for Nationalities，Lanzhou，Gansu 730030，China)

The Merrifield-Simmons index of a graph is defined as the total number of its independent sets．In this paper，We mainly discuss the number of a class of some-cycle graph Gm(n) with respect to Merrifield-Simmons index，and the specific expression is given．

some-cycle graph；Merrifield-Simmons index；counting

1004—5570(2016)06-0074-03

2016-09-19

國家民委科研項(xiàng)目(14XBZ018)；甘肅省自然科學(xué)基金(145RJZA158)；西北民族大學(xué)中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助研究生項(xiàng)目(Yxm2015180，Yxm2015182)；西北民族大學(xué)中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目(31920160064)

劉睿琳 (1993- )，女，甘肅永靖人，碩士生，研究方向：組合數(shù)學(xué)與圖論，E-mail: liuruilin0928@163.com．

O157.5

A