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

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

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

設(shè)e為圖G的一條邊,x為圖G的一個(gè)頂點(diǎn),將圖G刪去一條邊e后得到的圖記為G-e,圖G刪去一個(gè)頂點(diǎn)x及其關(guān)聯(lián)的所有邊后得到的圖記為G-x.在論文中沒(méi)有給出的術(shù)語(yǔ)和記號(hào)可參見(jiàn)文獻(xiàn)[17].

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

1 相關(guān)引理

引理1[1]設(shè)G是一個(gè)簡(jiǎn)單的連通圖,對(duì)?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]設(shè)Pn為n階的路,Cn為n階的圈，則：

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

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

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

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

2 主要結(jié)論及證明

定理1設(shè)圖G是n個(gè)頂點(diǎ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設(shè)圖G(Pm,Kn)是m×n個(gè)頂點(diǎn)的路粘完全圖，則

證明圖G(Pm,Kn)(圖1)去掉一個(gè)頂點(diǎn)vn得到的圖為G(Pm,Kn)-vn(圖2)，而圖G(Pm,Kn)-vn再去掉一個(gè)頂點(diǎn)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)式是關(guān)于m的遞推關(guān)系,所以由引理5可得其特征方程為x2-nx-n=0,對(duì)應(yīng)的特征根為

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

(2)

利用引理1，2，可以計(jì)算得遞推關(guān)系(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設(shè)圖G(Cm,Kn)是m×n個(gè)頂點(diǎn)的圈粘完全圖，則

證明圈粘完全圖G(Cm,Kn)(圖4)去掉一頂點(diǎn)vn得到圖G(Cm,Kn)-vn(圖2)，圖G(Cm,Kn)-vn去掉一頂點(diǎn)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的結(jié)論，得

3 結(jié)束語(yǔ)

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