几类图的Merrifield-Simmons指标及扇和轮的Hosoya指标

赵晓翠， 田双亮， 田文文

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

几类图的Merrifield-Simmons指标及扇和轮的Hosoya指标

赵晓翠， 田双亮， 田文文

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

摘要：Merrifield-Simmons指标和Hosoya指标是化学图论研究中两个重要的拓扑指标．在已有结论的基础上，主要研究了几类图的Merrifield-Simmons指标及 n阶的扇和轮的Hosoya指标，并给出了相应的递推公式，为以后研究化学分子结构的性质提供了重要的理论依据．

关键词：Merrifield-Simmons指标； 扇； 轮； Hosoya指标

1预备知识

令e和x分别为图G=(V,E)的一条边和一个顶点，我们用G-e表示图G删去边e得到的图，用G-x表示图G删去顶点x(及关联的边)得到的图．为计算方便，令 σ(G,0)=1,μ(G,0)=1．用NG(v)表示G中点v的邻点集，且NG[v]={v}∪NG(v)．

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

引理1[4]设G是一个简单图，对任意的u,v∈V(G)，uv∈E(G)，则

σ(G)=σ(G-V)+σ(G-NG[v])

且

μ(G)=μ(G-uv)+μ(G-u-v).

引理2[4]对于n阶的路Pn，有σ(Pn)=fn+2且μ(Pn)=fn+1.

引理3[4]若G1,G2，…，Gt是图G的连通分支，其中t≥2，则

引理4[4]对于n阶的圈Cn，有

σ(Cn)=fn+1+fn-1．

引理5 对于n阶的扇Fn(图1)，有

μ(Fn)=μ(Fn-1)+μ(Fn-2)+fn-1.

图1　扇Fn

图2　轮Wn

证明 根据引理1可得

μ(Fn)=μ(Fn-u0un-1)+μ(Fn-u0-un-1)=

μ(Fn-u0un-1-un-1un-2)+

μ(Fn-u0un-1-un-1-un-2)+μ(Pn-2)=

μ(P1)·μ(Fn-1)+μ(Fn-2)+fn-1=

f2·μ(Fn-1)+μ(Fn-2)+fn-1=

μ(Fn-1)+μ(Fn-2)+fn-1.

2主要结论及其证明

图3　Ln

证明由引理1、引理3可得

σ(Ln)= σ(Ln-vn)+σ(Ln-NLn[vn])=

σ(Ln-vn-un)+

σ(Ln-vn-NLn-vn[un])σ(Ln-NLn[vn])=

σ(Ln-1)+σ(Ln-1-un-1)+σ(Ln-1-vn-1)=

σ(Ln-1)+2σ(Ln-1-vn-1)=

(1)

而

σ(Ln-vn)=σ(Ln-vn-un)+

σ(Ln-vn-NLn-vn[un])=

σ(Ln-1)+σ(Ln-1-un-1)=

σ(Ln-1)+σ(Ln-1-vn-1)=

(2)

所以，由(1)、(2)可得

故

图4　Gn

证明由引理1、2、3可得

σ(Gn)=σ(Gn-vn-1)+σ(Gn-NGn[vn-1])=

σ(Gn-vn-1-un)+

σ(Gn-vn-1-NGn-vn-1[un])+

σ(P1)·σ(Gn-2)=

σ(Gn-1)+σ(Gn-vn-1-

NGn-vn-1[un]-vn-2)+

σ(Gn-vn-1-NGn-vn-1[un]-

NGn-vn-1-NGn-vn-1[un][vn-2])+2σ(Gn-2)=

σ(Gn-1)+σ(Gn-2)+σ(Gn-3)+2σ(Gn-2)=

σ(Gn-1)+3σ(Gn-2)+σ(Gn-3)=

其中

σ(G3)=σ(G3-v2)+

σ(G3-NG3[v2]=σ(P5)+[σ(P1)]3=

f7+(f3)2=13+23=21.

σ(G2)=σ(P4)=f6=8,

σ(G1)=[σ(P1)]2=22=4.

图5　Zn

证明由引理1、2、3及定理2可得

σ(Zn)=σ(Zn-vn-1)+σ(Zn-NZn[vn-1])=

σ(P1)·σ(Gn-1)+σ(Gn-2)=

定理4 对于如图6所示的图Mn，有

fn-1+fn+1

其中n≥7．

图6　Mn

证明由引理1、4、定理1及定理3可得

σ(Mn)=σ(Mn-a)+σ(Mn-NMn[a])=

σ(Mn-a-un)+

σ(Mn-a-NMn-a[un])+σ(Cn)=

σ(Mn-a-un-vn)+

σ(Mn-a-un-NMn-a-un[vn])+

σ(Mn-a-NMn-a[un])+fn-1+fn+1=

σ(Ln-1)+σ(Zn-2)+

σ(Zn-2)+fn-1+fn+1=

σ(Ln-1)+2σ(Zn-2)+fn-1+fn+1=

fn-1+fn+1.

定理5 对于如图1所示的扇图Fn(n≥3)，有

μ(Fn)=fn-2F1+fn-1F2+fn-2f2+

fn-3f3+…+fn-ifi+…+f1fn-1.

其中n-i≥1,i=1,2,…，n-1且F1=1,F2=2．

证明用第二数学归纳法证明k>3．

(1)当n=3时，μ(F3)=4=f1F1+f2F2+f1f2=1×1+1×2+1×1，定理成立；

(2)假设对一切n≤k，定理成立，则当n=k+1时，由引理5及假设可得

μ(Fk+1)=μ(Fk)+μ(Fk-1)+fk=

fk-2F1+fk-1F2+fk-2f2+

fk-3f3+…+fk-ifi+…+

f2fk-2+f1fk-1+fk-3F1+

fk-2F2+fk-3f2+fk-4f3+…+

fk-1-ifi+…+f1fk-2+fk=

(fk-2+fk-3)F1+

(fk-1+fk-2)F2+(fk-2+fk-3)f2+

(fk-3+fk-4)f3+…+

(fk-i+fk-1-i)fi+…+

(f2+f1)fk-2+f1fk-1+fk=

fk-1F1+fkF2+fk-1f2+

fk-2f3+…+fk+1-ifi+…+

f3fk-2+f1fk-1+fk=

fk-1F1+fkF2+fk-1f2+

fk-2f3+…+fk+1-ifi+…+

f3fk-2+f2fk-1+f1fk

注：f1=f2=1.

定理6 对于如图2所示的轮图Wn(n≥4)，有

μ(Wn)=(fn-2+fn-4)F1+

(fn-1+fn-3)F2+(fn-2+fn-4)f2+

(fn-3+fn-5)f3+…+

(fn-i+fn-2-i)fi+…+

(f3+f1)fn-3+f2fn-2+f1fn-1.

其中n-2-i≥1,i=1,2,…，n-3且F1=1,F2=2.

证明由引理1、2、3、5及定理5可得

μ(Wn)=μ(Wn-uvn-1)+μ(Wn-u-vn-1)=

μ(Wn-uvn-1-v1vn-1)+

μ(Wn-uvn-1-v1-vn-1)+μ(Pn-2)=

μ(Wn-uvn-1-v1vn-1-vn-1vn-2+

μ(Wn-uvn-1-v1vn-1-vn-1-vn-2)+

μ(Fn-2)+fn-1=

μ(P1)·μ(Fn-1)+μ(Fn-2)+

μ(Fn-2)+fn-1=

μ(Fn-1)+2μ(Fn-2)+fn-1=

μ(Fn)+μ(Fn-2)=

fn-2F1+fn-1F2+fn-2f2+

fn-3f3+…+fn-ifi+…+

f3fn-3+f2fn-2+f1fn-1=

fn-4F1+fn-3F2+fn-4f2+

fn-5f3+…+fn-2-ifi+…+f1fn-3=

(fn-2+fn-4)F1+

(fn-1+fn-3)F2+(fn-2+fn-4)f2+

(fn-3+fn-5)f3+…+

(fn-i+fn-2-i)fi+…+

(f3+f1)fn-3+f2fn-2+f1fn-1.

参考文献:

[1] Merrfield R E，Simmons H E．Topological methods in chemistry[M]．New York：Wiley，1989．

[2] Hosoya H．Topological index[J]．Bull Chem Soc Japan，1971，44：2 332-2 339．

[3] Gutman I．Acyclic systems with extremal Hückelπ-electron energy [J]．Theor．Chim，Acta,1997,45：79-87.

[4] Gutman I，Polansky O E．Mathematical concepts in organic chemistry[M]．Berlin：Springer，1986．

[5] Gutman I，Cyvin S J．Introduction to the theory of benzenoid hydrocarbons[M]．Berlin：Springer，1989．

[6] 张莲珠．两类四角系统的匹配数与点独立集数[J]．数学研究，1999，32(3)：310-315．

[7] Wagner S，Gutman I．Maxima and minima of the Hosoya Index and the Merrifield-Simmons index[J]．Acta Appl Math．2010，112：323-346．

[8] Chen X L，Zhao B，Zhao P Y．Six-membered ring spiro chains with extremal Merrifield-Simmons index and Hosoya index[J]．Math Comput Chem，2009，62(3)：657-665．

(编辑：姚佳良)