幾類圖的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．

(編輯：姚佳良)

收稿日期：2014-05-19

基金項目：西北民族大學中央高校科研專項資金資助研究生項目(ycx14029)

作者簡介：趙曉翠，女，397355370@qq.com； 通信作者： 田雙亮，男，sl_tian @163．com．

文章編號：1672-6197(2015)01-0027-05

中圖分類號：O157.5

文獻標志碼：A

The Merrifield-Simmons index of several graphs
and the Hosoya index of fan and wheel

ZHAO Xiao-cui， TIAN Shuang-liang， TIAN Wen-wen

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

Abstract:Merrifield-Simmonsindex and Hosoyaindex are the valuable topological indices in chemical graph theory．On the basis of the existing conclusions，this paper presents the Merrifield-Simmonsindex of several graphsand Hosoyaindex of fans and wheels with n vertices，and the recurrence formulas are given．Thisprovides an important theoretical basis for the further study of the nature of the chemical molecular structure．

Key words:Merrifield-Simmonsindex； fan； wheel； Hosoya index