刘睿琳，田双亮，田文文

(西北民族大学 数学与计算机科学学院，甘肃 兰州 730030)



一类多圈图关于Merrifield-Simmons指标的计数

刘睿琳，田双亮，田文文

(西北民族大学 数学与计算机科学学院，甘肃 兰州 730030)

图G的Merrifield-Simmons指标表示该图中所有独立集的数目。主要研究了一类多圈图Gm(n)关于Merrifield-Simmons指标的计数问题，并给出了具体的表达式。

多圈图；Merrifield-Simmons指标；计数

0 引言

自1989年美国化学家Merrifield和Simmons在文献[1]中提出Merrifield-Simmons指标之后，由于这一化学拓扑指标与物质的沸点有着密切的关系，且有着相当广泛的应用，参见文献[2,3]。随后，国内外很多学者对此进行了大量的研究工作，文献[4]中关于最大和最小的Merrifield-Simmons指标和Hosoya指标给出了一个很好的综述，并提出了一些有待解决的公开问题。文献[5]中研究了两类多元素链在不同构联接位下的Merrifield-Simmons指标的计数问题。文献[6]中研究了一类(n，n+2)-图关于两种拓扑指标的排序。本文研究了一类多圈图Gm(n)关于Merrifield-Simmons指标的计数问题，并给出了具体的表达式。文中未加说明的符号及术语参见文献[7]。

本文研究的多圈图Gm(n)是由n个m阶圈Cm(1),Cm(2),…,Cm(n)构成的圈序列，其中满足相邻两个圈之间只有一个公共顶点。

不妨设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)

在证明主要结论之前，先给出几个相关引理如下。

引理1[2]设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 主要结论及其证明

引理4 对于如图2所示的图H，其Merrifield-Simmons指标为：

图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指标为：

σ(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 对于如……