馬海成， 李丹陽(yáng)

(青海民族大學(xué) 數(shù)學(xué)學(xué)院， 青海 西寧 810007)

0 引 言

本文僅考慮有限無(wú)向的簡(jiǎn)單圖. 設(shè)G是有n個(gè)點(diǎn)的圖，G的一個(gè)匹配是指G的 一個(gè)生成子圖，它的每個(gè)連通分支或是孤立點(diǎn)或是孤立邊. 恰有k條邊的匹配稱(chēng)為k-匹配. 在文獻(xiàn)[1]中圖G的匹配多項(xiàng)式定義為

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

匹配多項(xiàng)式在數(shù)學(xué)、統(tǒng)計(jì)物理和化學(xué)中都有很重要的應(yīng)用. 在統(tǒng)計(jì)物理上，它是描述一種物理系統(tǒng)的數(shù)學(xué)模型，首先由物理學(xué)家Heilmann等[2]為研究這種物理系統(tǒng)引進(jìn)圖的匹配多項(xiàng)式. 在理論化學(xué)中，匹配多項(xiàng)式根的絕對(duì)值的和稱(chēng)為該圖的匹配能量，它與這個(gè)圖所表示的芳香烴的活性有關(guān)[3]. 它的所有系數(shù)絕對(duì)值的和(即所有匹配的總數(shù))就是這個(gè)圖表示的碳?xì)浠衔锏腍osoya指標(biāo)，它與這個(gè)化合物的沸點(diǎn)有關(guān)[4].匹配多項(xiàng)式是一種組合計(jì)數(shù)多項(xiàng)式，它與圖的特征多項(xiàng)式、色多項(xiàng)式和其他多項(xiàng)式有許多聯(lián)系[5-7]. 對(duì)于無(wú)圈圖，它等于特征多項(xiàng)式；對(duì)于一般圖，它是該圖路樹(shù)的特征多項(xiàng)式的一個(gè)因式[8-9]. 它有許多優(yōu)美性質(zhì)， 如它的根都是實(shí)數(shù)， 且關(guān)于坐標(biāo)原點(diǎn)對(duì)稱(chēng)[1]；它的某種形式的積分可以計(jì)算滿(mǎn)足某些不等式條件的置換個(gè)數(shù)[1]； 它的另一種形式的積分可以計(jì)算該圖的匹配能量[3]. 目前，對(duì)于匹配多項(xiàng)式的研究有很多[1-13],但對(duì)于匹配根取值范圍的研究還很少見(jiàn)，本文研究了包含一個(gè)∞-圖為其導(dǎo)出子圖的一類(lèi)雙圈圖匹配最大根的取值范圍.

圖1 圖和

圖2 圖θ(a,b,c)、∞(a,s,b)和∞(a,b)Fig.2 The graphs θ(a,b,c)、∞(a,s,b) and ∞(a,b)

設(shè)G是有n個(gè)點(diǎn)的一個(gè)圖，恰有n-1、n和n+1條邊的連通圖分別稱(chēng)為樹(shù)、單圈圖和雙圈圖. 眾所周知, 雙圈圖有兩類(lèi)，包含導(dǎo)出子圖θ(a,s,t)的雙圈圖的集合記為Β1，若G∈Β1, 稱(chēng)G是第一類(lèi)雙圈圖. 包含導(dǎo)出子圖∞(a,s,b)或∞(a,b)的雙圈圖的集合記為Β2， 若G∈Β2, 稱(chēng)G是第二類(lèi)雙圈圖. 以M1(G)表示圖G的匹配多項(xiàng)式μ(G,x)的最大根，簡(jiǎn)稱(chēng)為匹配最大根.本文研究了第二類(lèi)雙圈圖的匹配最大根的取值范圍，主要結(jié)論是下面的定理.

定理設(shè)G是有n個(gè)點(diǎn)的第二類(lèi)連通雙圈圖,G∈Β2,則

(2)當(dāng)n=5,M1(∞(2,2))≤M1(G), 僅當(dāng)G?θ(2,2)時(shí)取等號(hào).

(3)當(dāng)n≥6,M1(∞(2,n-6,2))≤M1(G),僅當(dāng)兩個(gè)圖同構(gòu)時(shí)取等號(hào).

1 若干引理

引理1[1]設(shè)圖G有k個(gè)連通分支G1,G2,…,Gk, 則

μ(G,x)=μ(G1,x)μ(G2,x)…μ(Gk,x).

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

(2)μ(G,x)=μ(Ge,x)-μ(G{u,v},x).

引理3設(shè)G是一個(gè)圖，u∈V(G),e=uv∈E(G), 則

(1)匹配多項(xiàng)式μ(G,x)的根都是實(shí)數(shù).

(2)M1(G)≥M1(Gu), 若G連通，則M1(G)>M1(Gu).

(3)M1(G)≥M1(Ge), 若G連通，則M1(G)>M1(Ge).

證明(1)、(2)見(jiàn)文獻(xiàn)[1].

(3)由于μ(G,x)=μ(Ge,x)-μ(G{u,v},x)，而μ(G,x)的最大根大于等于μ(G{u,v},x)的最大根，這說(shuō)明，當(dāng)x≥M1(G)時(shí)，μ(G{u,v},x)≥0. 引理2(2)也隱含著μ(G,x)的最大根大于等于μ(Ge,x)的最大根. 若G連通，μ(G,x)的最大根大于μ(G{u,v},x)的最大根，這說(shuō)明，當(dāng)x≥M1(G)時(shí)，μ(G{u,v},x)>0.這也隱含著μ(G,x)的最大根大于μ(Ge,x)的最大根.

□

引理4[14]設(shè)P(s,t)=Ps∪Pt,k≤s≤t是整數(shù)，則

μ(P(s,t))-μ(P(s-k,t+k))=

μ(P(k-1,t-s+k-1)).

約定μ(P0)=1,μ(P-1)=0,引理4對(duì)k≥0的整數(shù)都是對(duì)的.

設(shè)G是一個(gè)連通圖，e=uv∈E(G),且u和v在圖G中沒(méi)有公共鄰點(diǎn)，即N(u)∩N(v)=φ. 構(gòu)造一個(gè)圖G(e)如下：先從圖G中刪除邊e, 然后黏結(jié)點(diǎn)u和v成為一個(gè)點(diǎn)w, 最后在點(diǎn)w依附一個(gè)懸掛點(diǎn)z,見(jiàn)圖3. 記e′=wz. 明顯的，當(dāng)e是G的一條懸掛邊時(shí)，G?G(e). 將圖G變?yōu)镚(e)的圖變換稱(chēng)為第一種圖變換.

圖3 圖G和G(e)Fig.3 The graphs G and G(e)

引理5設(shè)d(u)≥2,d(v)≥2,N(u)∩N(v)=φ, 則

μ(G)-μ(G(e))=

證明由引理2(1),

μ(G{u,v})=

x[xμ(G{u,v})-

μ(G(e))=xμ(G(e)w)-

由圖G(e)的構(gòu)造知,

x2μ(G{u,v})=xμ(G(e)w),

且

μ(G{u,v})=μ(G(e){w,z}),

μ(G)-μ(G(e))=

□

設(shè)G是至少有兩個(gè)點(diǎn)的連通圖,u∈V(G), 路Pn的點(diǎn)從一端到另一端分別標(biāo)記為v1,v2,…,vn,圖G的點(diǎn)u和路Pn的點(diǎn)vi黏結(jié)后得到的圖記為Gu,iPn(圖4). 將圖Gu,iPn變?yōu)镚u,1Pn的圖變換叫第二種圖變換.

圖4 圖Gu,iPnFig.4 The graph Gu,iPn

引理6設(shè)G是至少有兩個(gè)點(diǎn)的連通圖,u∈V(G),n≥3,1

μ(Gu,1Pn)-μ(Gu,iPn)=

證明與引理5的證明類(lèi)似，略.

□

圖5 圖和

引理7設(shè)G、H1和H2是三個(gè)連通圖,u,v∈V(G),u′∈V(H1),u″∈V(H2), 則

證明與引理5的證明類(lèi)似，略.

□

在圖G的自同構(gòu)群下屬于同一軌道上的點(diǎn)稱(chēng)為相似點(diǎn), 點(diǎn)u和v在圖G中相似當(dāng)且僅當(dāng)存在G的一個(gè)自同構(gòu)π, 使得π(u)=v.

推論設(shè)G、H1和H2是三個(gè)連通圖,u,v∈V(G),u′∈V(H1),u″∈V(H2), 且點(diǎn)u和v在圖G中相似, 則

證明由點(diǎn)u和v在圖G中相似,可以得到

由引理7得證.

□

設(shè)G是一個(gè)圖,e=uv∈E(G), 在邊e中依次插入n個(gè)點(diǎn)v1,v2,…,vn后得到的圖記為Ge,n(圖6). 圖Gu,1Pn+1的記號(hào)同引理6. 將圖Gu,1Pn+1變?yōu)镚e,n的圖變換叫第四種圖變換.

圖6 圖Gv,1Pn+1和Ge,nFig.6 The graphs Gv,1Pn+1 and Ge,n

引理8設(shè)G是一個(gè)連通,e=uv∈E(G), 則

μ(Ge,n)-μ(Gv,1Pn+1)=

證明與引理5的證明類(lèi)似，略.

□

2 主要定理的證明

引理9設(shè)G1,G2是兩個(gè)n階連通圖，如果存在圖G1的真子圖Hi(i=1,2,…,s), 滿(mǎn)足

則

M1(G1)

證明由引理3知,μ(G)的最大根大于μ(Hi)的最大根，說(shuō)明當(dāng)x≥M1(G)時(shí),

這也隱含著μ(G2)的最大根大于μ(G1)的最大根.

□

設(shè)G是一個(gè)連通圖,u∈V(G)、(T,v)是帶有根點(diǎn)v的一棵n(≥2)階樹(shù), 以Gu,vT表示將圖G的點(diǎn)u和T的點(diǎn)v黏結(jié)后得到的圖,K1,n-1為n個(gè)點(diǎn)的星圖, 中心點(diǎn)記為w.

引理10設(shè)G是一個(gè)連通圖,u∈V(G),(T,v)是帶有根點(diǎn)v的一棵n(≥2)階樹(shù), 則

M1(Gu,vT)≤M1(Gu,wK1,n-1)，

僅當(dāng)Gu,vT?Gu,wK1,n-1時(shí)取等號(hào).

證明對(duì)圖Gu,vT的G與T之間的割邊重復(fù)地使用第一種圖變換和引理9,得證.

□

引理11設(shè)G是一個(gè)連通圖,u∈V(G),(T,v)是帶有根點(diǎn)v的一棵n(≥2)階樹(shù), 則

M1(Gu,1Pn)≤M1(Gu,vT),

僅當(dāng)Gu,vT?Gu,1Pn時(shí)取等號(hào).

證明對(duì)圖Gu,vT的樹(shù)T上的距離點(diǎn)v最遠(yuǎn)的分叉點(diǎn)(度數(shù)大于2的點(diǎn))重復(fù)地使用第二種圖變換和引理9，得證.

□

注意在圖∞(a,s,b)中, 兩邊的參數(shù)a和b分別表示兩個(gè)圈上的點(diǎn)數(shù)是a+1和b+1, 中間的參數(shù)s表示兩個(gè)圈之間的軸上的點(diǎn)數(shù)(不包括圈上的點(diǎn)), 下面的引理給出在一定條件下, 將圈上的點(diǎn)移動(dòng)到軸上后的匹配多項(xiàng)式之間的關(guān)系.

引理12 設(shè)3≤a,0≤s, 2≤b, 且a≤b+s+3, 則

μ(∞(a,s,b))-μ(∞(a-1,s+1,b))=

證明由引理2(2)知,

μ(∞(a,s,b))=μ(Q(b,s+a+1))-

μ(Q(b,s)∪Pa-1),

μ(∞(a-1,s+1,b))=μ(Q(b,s+a+1)-

μ(Q(b,s+1)∪Pa-2),則

μ(∞(a,s,b))-μ(∞(a-1,s+1,b))=

μ(Q(b,s+1)∪Pa-2)-μ(Q(b,s)∪Pa-1)=

[μ(Pb+s+2)-μ(P(b-1,s+1))]μ(Pa-2)-

[μ(Pb+s+1)-μ(P(b-1,s))]μ(Pa-1)=

[μ(P(b+s+2,a-2))-μ(P(b+s+1,a-1))]-

μ(Pb-1)[μ(P(s+1,a-2))-μ(P(s,a-1))].

(1)當(dāng)a≤s+1, 即s≥a-1, 此時(shí)必有b+s+1≥a-1,由引理4知

μ(∞(a,s,b))-μ(∞(a-1,s+1,b))=

-μ(Pb+s-a+2)+μ(P(b-1,s-a+1))=

-μ(Q(b,s-a+1)).

(2)當(dāng)a=s+2, 即s+1=a-1, 此時(shí)必有b+s+1≥a-1,由引理4知

μ(∞(a,s,b))-μ(∞(a-1,s+1,b))=

-μ(Pb+s-a+2).

(3)當(dāng)s+3≤a≤b+s+2, 即a-2≥s+1且b+s+1≥a-1,由引理4知

μ(∞(a,s,b))-μ(∞(a-1,s+1,b))=

-μ(Pb+s-a+2)-μ(P(b-1,a-s-3)).

(4)當(dāng)a=b+s+3, 此時(shí)必有a-2≥s+1, 由引理4知

μ(∞(a,s,b))-μ(∞(a-1,s+1,b))=

-μ(P(b-1,a-s-3)).

引理13設(shè)2≤a,0≤s,2≤b, 且b+s+4≤a, 則

μ(∞(a,s,b))-μ(∞(s+2,a-2,b))=

-2μ(P(a-s-3,b-1)).

證明由引理2(2)知,

μ(∞(a,s,b))=μ(Q(b,s+a+1))-

μ(Q(b,s)∪Pa-1),

μ(∞(s+2,a-2,b))=μ(Q(b,s+a+1)-

μ(Q(b,a-2)∪Ps+1),則

μ(∞(a,s,b))-μ(∞(s+2,a-2,b))=

μ(Q(b,a-2)∪Ps+1)-μ(Q(b,s)∪Pa-1)=

[μ(Pb+a-1)-μ(P(b-1,a-2))]μ(Ps+1)-

[μ(Pb+s+1)-μ(P(b-1,s))]μ(Pa-1)=

[μ(P(s+1,b+a-1))-μ(P(a-1,b+s+1))]-

μ(Pb-1)[μ(P(s+1,a-2))-μ(P(s,a-1))]=

-μ(P(a-s-3,b-1))-

μ(P(a-s-3,b-1))=

-2μ(P(a-s-3,b-1)).

□

引理14 設(shè)3≤a,2≤b, 則

μ(∞(a,b))-μ(∞(2,a-3,b))=

-μ(P(b-2,a-3))-μ(P(1,b-1,a-3)).

證明由引理2(2)知,

μ(∞(a,b))=μ(Q(b,a))-μ(P(b,a-1)),

μ(∞(2,a-3,b))=μ(Q(b,a))-μ(P1∪

Q(b,a-3)),則

μ(∞(a,b))-μ(∞(2,a-3,b))=

μ(P1∪Q(b,a-3))-μ(P(b,a-1))=

[μ(P(1,b+a-2))-μ(P(b,a-1))]-

μ(P(1,b-1,a-3))=-μ(P(b-2,a-3))-

μ(P(1,b-1,a-3)).

□

圖7 圖

由于

此時(shí)引理7變?yōu)?/p>

由引理9, 得到定理的(1).

由引理11, 將依附于∞-的每棵樹(shù)替換成同樣點(diǎn)數(shù)的路, 其匹配最大根會(huì)減小. 再重復(fù)使用第四種圖變換, 逐步將∞-上懸掛的路變?yōu)閮?nèi)部路, 最后變?yōu)橐粋€(gè)n階的圖∞(a′,s′,b′)或∞(a′,b′), 由引理8, 其匹配最大根會(huì)減小.

5個(gè)點(diǎn)的∞圖只有一種, 即∞(2,2), 因此, 定理的(2)成立.

(3)n≥6,如果∞(a,s,b)不同構(gòu)于∞(2,n-6,2).

(i)當(dāng)a≤b+s+3時(shí), 由引理12和引理9知,M1(∞(2,s+a-2,b))

(ii)當(dāng)a≥b+s+4時(shí)，由引理13和引理9知，M1(∞(s+2,a-2,b))

不論是(i)還是(ii), 均得到M1(∞(2,s+a-2,b))

(iii)對(duì)圖∞(a,b),由引理14及上面的(i)和(ii)知，M1(∞(2,n-6,2))

□