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

吳量,劉小花,汪一航

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

1 引言

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

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

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

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

以Pn,Cn,Kn,Tn分別表示n個(gè)點(diǎn)的路、圈、完全圖和樹.以G∪H表示兩個(gè)圖G和G的并圖.把形似“心”的圖稱為心形圖,它是路Pa+2的首尾兩個(gè)點(diǎn)與圈C4的某條邊的兩個(gè)端點(diǎn)分別粘結(jié)在一起,且路Pb+2的首尾兩個(gè)點(diǎn)與它的相鄰邊的兩個(gè)端點(diǎn)互相粘結(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個(gè)連通分支,μ(Gi)表示第i個(gè)分支圖的匹配多項(xiàng)式,則

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

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

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

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

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

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

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

證明由引理2.3知,

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

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

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

則:(1)n?m是一個(gè)偶數(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個(gè)點(diǎn)的圖,則

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

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

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

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

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

同理,

則有

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

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

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

由引理2.6的(1)得,

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

由引理2.6的(2)得,

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

由引理2.6的(2)得,

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

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

與 (1)的(i)類似,當(dāng)2≤l≤k時(shí),只需取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時(shí),

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

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

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

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

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

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

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

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

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

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

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

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

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

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

與 (1)的(i)類似,當(dāng)2≤l≤k時(shí),只需取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時(shí),ME(G(2l+1,4,4k?2l+2))>ME(G(2l?1,4,4k?2l+4)).

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

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

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

定理3.2 設(shè)G(a,4,b)(a≥1,b≥1)是a+4+b個(gè)點(diǎn)的圖，則它的Hosoya指標(biāo)排序?yàn)?/p>

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

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

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

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