一類雙圈圖匹配多項式的最大根

馬海成， 李丹陽

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

0 引 言

本文僅考慮有限無向的簡單圖. 設G是有n個點的圖，G的一個匹配是指G的 一個生成子圖，它的每個連通分支或是孤立點或是孤立邊. 恰有k條邊的匹配稱為k-匹配. 在文獻[1]中圖G的匹配多項式定義為

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

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

圖1 圖和

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

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

定理設G是有n個點的第二類連通雙圈圖,G∈Β2,則

(2)當n=5,M1(∞(2,2))≤M1(G), 僅當G?θ(2,2)時取等號.

(3)當n≥6,M1(∞(2,n-6,2))≤M1(G),僅當兩個圖同構時取等號.

1 若干引理

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

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

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

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

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

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

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

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

證明(1)、(2)見文獻[1].

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

□

引理4[14]設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對k≥0的整數(shù)都是對的.

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

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

引理5設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)的構造知,

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

且

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

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

□

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

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

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

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

證明與引理5的證明類似，略.

□

圖5 圖和

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

證明與引理5的證明類似，略.

□

在圖G的自同構群下屬于同一軌道上的點稱為相似點, 點u和v在圖G中相似當且僅當存在G的一個自同構π, 使得π(u)=v.

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

證明由點u和v在圖G中相似,可以得到

由引理7得證.

□

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

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

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

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

證明與引理5的證明類似，略.

□

2 主要定理的證明

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

則

M1(G1)

證明由引理3知,μ(G)的最大根大于μ(Hi)的最大根，說明當x≥M1(G)時,

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

□

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

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

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

僅當Gu,vT?Gu,wK1,n-1時取等號.

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

□

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

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

僅當Gu,vT?Gu,1Pn時取等號.

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

□

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

引理12 設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)當a≤s+1, 即s≥a-1, 此時必有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)當a=s+2, 即s+1=a-1, 此時必有b+s+1≥a-1,由引理4知

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

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

(3)當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)當a=b+s+3, 此時必有a-2≥s+1, 由引理4知

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

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

引理13設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 設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 圖

由于

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

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

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

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

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

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

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

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

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

□