心形圖的匹配能序及Hosoya指標(biāo)排序

吳量,劉小花,汪一航

(1.寧波大學(xué)理學(xué)院,浙江 寧波 315211;2.青海民族大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院,青海 西寧 810007)

1 引言

本文僅考慮有限無向的簡單圖.設(shè)一個圖G=(V,E)是n個點的連通圖,其中V是非空的頂點集,E是非空邊集,且A(G)是G的鄰接矩陣,圖G的特征多項式Φ(G)在文獻[1]中被定義為:這里I是n個點的恒等矩陣.等式 Φ(G)=0的根λ1,λ2,···,λn稱為A(G)的特征根.G的能級E(G)被定義為A(G)的特征根的絕對值的和,記為能級定義自1978年被提出以來,前人已做了大量的研究,許多成果層出不窮,參看專著[4].

設(shè)G是n個點的圖,所謂G的一個匹配是指的一個生成子圖,它的每個分支或是孤立點或是孤立邊.恰有k條邊的匹配稱為k-匹配.在文獻[1]中匹配多項式定義為:

這里m(G,k)是G中的k-匹配的數(shù)目.為了方便,本文中將μ(G,x)簡記為μ(G).

匹配多項式是一種計數(shù)多項式,它在數(shù)學(xué),統(tǒng)計物理和化學(xué)都有著很重要的應(yīng)用.在統(tǒng)計物理上,匹配多項式是描述一種物理系統(tǒng)的數(shù)學(xué)模型,物理學(xué)家Heilmann和Lieb為了研究此物理系統(tǒng)引進了圖的二元匹配多項式,見文獻[2].在理論化學(xué)中,它的系數(shù)的絕對值的和(即所有的匹配總數(shù))就是這個圖所表示的碳?xì)浠衔锏腍osoya指標(biāo),記為該指標(biāo)與這個化合物的沸點有關(guān),參看文獻[3].匹配多項式的根的絕對值的和稱為圖的匹配能級,它與這個圖所表示的芳香烴的活性有關(guān),見文獻[5].文獻[8]也提到匹配能級是一個與化學(xué)應(yīng)用相關(guān)的量,得出了一個簡單的關(guān)系:TRE(G)=E(G)?ME(G),這里TRE(G)被稱作拓?fù)涔舱衲芰?關(guān)于匹配能級的化學(xué)應(yīng)用,詳細(xì)信息見文獻[7].前人對圖的能級已經(jīng)有了大量的研究,然而,對圖的匹配能級的研究較為少見.

以Pn,Cn,Kn,Tn分別表示n個點的路、圈、完全圖和樹.以G∪H表示兩個圖G和G的并圖.把形似“心”的圖稱為心形圖,它是路Pa+2的首尾兩個點與圈C4的某條邊的兩個端點分別粘結(jié)在一起,且路Pb+2的首尾兩個點與它的相鄰邊的兩個端點互相粘結(jié),所得到的圖稱為心形圖,記為G(a,4,b)(a≥1,b≥1),(見圖1).在這篇文章中得到了心形圖之間的匹配能序以及他們的Hosoya指標(biāo)排序.

圖1 心形圖G(a,4,b)(a≥1,b≥1)

2 若干引理

引理2.1[1]設(shè)圖G有k個連通分支,μ(Gi)表示第i個分支圖的匹配多項式,則

引理2.2[1]設(shè)G是一個圖,e=uv∈E(G),則

這里μ(Gu,x),μ(G{u,i},x)分別表示從圖G中刪去點u所得到的圖的匹配多項式,從圖G中刪去點u和點i(這里的i表示與u相關(guān)聯(lián)的點)所得到的圖的匹配多項式.

(2)μ(G,x)=μ(G?e,x)?μ(G{u,v},x).

這里μ(G?e,x),μ(G{u,v},x)分別表示從圖G中刪去邊e所得到的圖的匹配多項式,從圖G中刪去點u和點v所得到的圖的匹配多項式.

引理2.3設(shè)Pn是n個點的路,則

證明由引理2.2和引理2.1,顯然.

引理2.4設(shè)Pn是n個點的路,k是下面有意義的整數(shù),則

證明由引理2.3知,

引理2.5[3]設(shè)G是一個圖,則,這里m(G,k)是G中的k-匹配的數(shù)目,k=0,1,2,···.

由引理 2.5和對數(shù)函數(shù)的單調(diào)性,規(guī)定一種偏序關(guān)系 “?”.設(shè)G1,G2是兩個n階圖,由引理 2.5的單調(diào)性,對所有的非負(fù)整數(shù)k,若滿足m(G1,k)≤m(G2,k),則G1?G2.進一步,如果不等式m(G1,k)

引理2.6[7]設(shè)G1,G2是兩個n階圖,如果存在一個m階圖H,滿足

則:(1)n?m是一個偶數(shù);(2)如果n?m≡0(mod 4),則ME(G1)>ME(G2);(3)如果n?m≡2(mod 4),則ME(G1)

3 主要定理及證明

定理3.1 設(shè)G(a,4,b)(a≥1,b≥1)是a+4+b個點的圖,則

(1)當(dāng)a+b=4k時,

(2)當(dāng)a+b=4k+1時,

(3)當(dāng)a+b=4k+2時,

(4)當(dāng)a+b=4k+3時,

證明由引理2.1,兩次運用刪邊的方法,分別刪去圖1中的e1,e2,得

同理,

則有

由引理2.3,引理2.4可以推得上式.

(1)當(dāng)a+b=4k時,

(i)當(dāng)取a=2l,b=4k?2l(2≤l≤k)時,

由引理2.6的(1)得,

(ii)當(dāng)取a=2l,b=4k?2l(l=k)時,

由引理2.6的(2)得,

(iii)當(dāng)取a=2l?1,b=4k?2l+1(2≤l≤k)時,

由引理2.6的(2)得,

(2)當(dāng)a+b=4k+1時,

(i)證明當(dāng)2≤l≤k時,

與 (1)的(i)類似,當(dāng)2≤l≤k時,只需取a=2l,b=4k?2l+1,

由引理2.6的(1)得,結(jié)論成立.

(ii)證明

與(1)的(ii)類似,只需取a=2k,b=2k+1,(l=k),

由引理2.6的(2)得,結(jié)論成立.

(iii)證明當(dāng)2≤l≤k時,

與(1)的(iii)類似,當(dāng)2≤l≤k時,只需取a=2l?1,b=4k?2l+2,

由引理2.6的(2)得,結(jié)論成立.

(3)當(dāng)a+b=4k+2時,

(i)證明當(dāng)2≤l≤k時,ME(G(2l?2,4,4k?2l+4))>ME(G(2l,4,4k?2l+2)).

與(1)的(i)類似,當(dāng)2≤l≤k時,只需取a=2l,b=4k?2l+2,

由引理2.6的(1)得,結(jié)論成立.

(ii)ME(G(2k,4,2k+2))>ME(G(2k+1,4,2k+1)).

事實上,與 (1)的(ii)類似,只需取a=2k+1,b=2k+1(l=k),

由引理2.6的(2)得,結(jié)論成立.

(iii)證明當(dāng)2≤l≤k時,

與 (1)的(iii)類似,當(dāng)2≤l≤k時,只需取a=2l+1,b=4k?2l+1,

由引理2.6的(2)得,結(jié)論成立.

(4)當(dāng)a+b=4k+3時,

(i)證明當(dāng)2≤l≤k時,

與 (1)的(i)類似,當(dāng)2≤l≤k時,只需取a=2l,b=4k?2l+3,

由引理2.6的(1)得,結(jié)論成立.

(ii)證明ME(G(2k,4,2k+3))>ME(G(2k+1,4,2k+2)).

與 (1)的(ii)類似,只需取a=2k+1,b=2k+2,

由引理2.6的(1)得,結(jié)論成立.

(iii)證明當(dāng)2≤l≤k時,ME(G(2l+1,4,4k?2l+2))>ME(G(2l?1,4,4k?2l+4)).

與 (1)的(iii)類似,當(dāng)2≤l≤k時,只需取a=2l+1,b=4k?2l+2,

由引理2.6的(2)得,結(jié)論成立.

由引理2.5的積分公式,根據(jù)對數(shù)函數(shù)的單調(diào)性,很明顯可以看出,G的匹配能級隨著m(G,k)單調(diào)遞增,再由Hosoya指標(biāo)的定義及定理3.1容易得下面的定理:

定理3.2 設(shè)G(a,4,b)(a≥1,b≥1)是a+4+b個點的圖，則它的Hosoya指標(biāo)排序為

(1)當(dāng)a+b=4k時

(2)當(dāng)a+b=4k+1時

(3)當(dāng)a+b=4k+2時

(4)當(dāng)a+b=4k+3時