蘇曉海，孫澤清,俞天仕，高 云，任勝章

(陜西理工大學 數(shù)學與計算機科學學院，陜西 漢中 723001)

設圖G(V,E)是簡單的連通無向圖，并且V(G)和E(G)分別是它的頂點集和邊集，分別簡記為V和E.稱集合A為圖G的一個獨立集,如果A?V(G)，對于任意的兩個頂點u,v∈A,都有uv?E(G)成立,其中空集為任何圖的一個獨立集[1-8].圖G的Merrifield-Simmons指標是指圖G的獨立集的個數(shù)，記為σ(G).圖的Merrifield-Simmons指標是由Richard E.Merrifield和Howard E.Simmons兩位美國化學家在1989年引入的拓撲指標[7-9].Merrifield-Simmons指標在化學圖論中具有非常重要的作用,該指標與烷烴的物理化學性質尤其是與物質的沸點有著密切聯(lián)系，且在有機化合物的合成和新藥物的研發(fā)領域有著較為廣泛的應用.

設e為圖G的一條邊,x為圖G的一個頂點,將圖G刪去一條邊e后得到的圖記為G-e,圖G刪去一個頂點x及其關聯(lián)的所有邊后得到的圖記為G-x.在論文中沒有給出的術語和記號可參見文獻[17].

論文中將Fibonacci數(shù)簡記為Fn,滿足Fn=Fn-1+Fn-2,n≥2,且F0=0,F1=1.Cn表示含有n個頂點的圈；Kn表示n階完全圖；G(Pm,Kn)是由一條m個頂點的路的每個頂點上粘接一個n階完全圖Kn得到的連通圖，稱之為路粘完全圖(圖1)；G(Cm,Kn)表示由圈Cm的每個頂點上粘接一個n階完全圖Kn得到的圖，稱之為圈粘完全圖(圖4).論文主要研究路粘完全圖G(Pm,Kn)和圈粘完全圖G(Cm,Kn)的Merrifield-Simmons指標，并分別給出了其Merrifield-Simmons指標的計算公式.

1 相關引理

引理1[1]設G是一個簡單的連通圖,對?uv∈E(G),u∈V(G),令NG[u]={v|uv∈E(G)},則

σ(G)=σ(G-u)+σ(G-NG[u]).

(3)F(m)L(n)=F(n+m)-(-1)mF(n-m)=F(m+n)+(-1)nF(m-n).

引理4[1]設Pn為n階的路,Cn為n階的圈，則：

(1)σ(Pn)=Fn+2；

(2)σ(Cn)=Fn+1+Fn-1.

引理5[4]設實數(shù)組q1,q2,…,qt是常系數(shù)齊次遞推關系式H(n)=a1H(n-1)+a2H(n-2)+…+akH(n-k)的特征方程的所有互不相等的特征根,并且它們的重數(shù)依次為e1,e2,…,et,則遞推關系對應于qi部分的解為Hi(n)=(c1+c2n+…+ceinei-1)qin,而遞推關系式的一般解為

H(n)=H1(n)+H2(n)+…+Ht(n).

2 主要結論及證明

定理1設圖G是n個頂點的完全圖，則

σ(Kn)=n+1.

證明已知σ(?)=1,由引理1，有

σ(Kn)=σ(Kn-u)+σ(Kn-NG[u])=σ(Kn-1)+σ(?)=

σ(Kn-1)+1=σ(Kn-2)+σ(?)+1=…=

σ(K3)+n-3=4+n-3=n+1.

定理2設圖G(Pm,Kn)是m×n個頂點的路粘完全圖，則

證明圖G(Pm,Kn)(圖1)去掉一個頂點vn得到的圖為G(Pm,Kn)-vn(圖2)，而圖G(Pm,Kn)-vn再去掉一個頂點vn-1得到的圖為G(Pm,Kn)-vn-vn-1(圖3).

圖1 路粘完全圖G(Pm,Kn)

圖2 圖G(Pm,Kn)-vn

圖3 圖G(Pm,Kn)-vn-vn-1

由引理1，2，得

σ[G(Pm,Kn)]=σ[G(Pm,Kn)-vn]+σ[G(Pm,Kn)-NG[vn]]=

σ[(Kn-1)G(Pm-1,Kn)]+σ[(Kn-1)G(Pm-2,Kn)]=

nσ[G(Pm-1,Kn)]+nσ[G(Pm-2,Kn)]，

即

σ[G(Pm,Kn)]=nσ[G(Pm-1,Kn)]+nσ[G(Pm-2,Kn)].

(1)

由于(1)式是關于m的遞推關系,所以由引理5可得其特征方程為x2-nx-n=0,對應的特征根為

所以遞推關系(1)的通解為

(2)

利用引理1，2，可以計算得遞推關系(1)的初始值為

σ[G(P2,Kn)]=n(n+1)+n=n2+2n,

σ[G(P3,Kn)]=nσ[G(P2,Kn)]+n(n+1)=n(n2+2n)+n2+n=n3+3n2+n.

把初始值代入(2)式得到以A,B為未知參數(shù)的方程組為

(3)

解方程組(3)，得

(4)

再將(4)式代入(2)式，得

證畢.

定理3設圖G(Cm,Kn)是m×n個頂點的圈粘完全圖，則

證明圈粘完全圖G(Cm,Kn)(圖4)去掉一頂點vn得到圖G(Cm,Kn)-vn(圖2)，圖G(Cm,Kn)-vn去掉一頂點v1得到圖G(Cm,Kn)-vn-vn-1(圖5).

圖4 圈粘完全圖G(Cm,Kn)

圖5 圖G(Cm,Kn)-vn

由引理1，2，得

σ[G(Cm,Kn)]=σ(G-vn)+σ(G-NG[vn])=σ(kn-1G(Pm-1,Kn))+σ(kn-1G(Pm-3,Kn)kn-1)=

nσ[G(Pm-1,Kn)]+n2σ[G(Pm-3,Kn)]，

即

σ[G(Cm,Kn)]=nσ[G(Pm-1,Kn)]+n2σ[G(Pm-3,Kn)].

(5)

再利用定理2的結論，得

3 結束語

首先應用常系數(shù)齊次遞推關系式的性質得出n階完全圖Kn的Merrifield-Simmons指標計算公式；其次利用n階完全圖Kn的Merrifield-Simmons指標計算公式，應用常系數(shù)齊次遞推關系式的性質得出了路粘完全圖G(Pm,Kn)的Merrifield-Simmons指標的計算公式；最后通過應用定理1,2的結論得出圈粘完全圖G(Cm,Kn)的Merrifield-Simmons指標的計算公式.