“8”字圖的匹配能級(jí)和Hosoya指標(biāo)全排序?

馬海成，劉小花

(青海民族大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，青海 西寧810007)

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

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

定義1 設(shè)λ1,λ2,…,λn是圖G的匹配多項(xiàng)式的所有根，定義它的匹配能級(jí)為：

匹配能級(jí)的概念衍生自是圖的能級(jí)，所謂圖的能級(jí)是這個(gè)圖的譜的絕對(duì)值的和，即所有特征根的絕對(duì)值的和。在Hückel分子軌道理論中，共軛碳?xì)浠衔锏姆肿拥摩?電子能量水平近似地等于該分子圖的能級(jí)。對(duì)圖的能級(jí)已有了大量的研究，見(jiàn)專(zhuān)著[5]。由于無(wú)圈圖的特征多項(xiàng)式等于匹配多項(xiàng)式[1]，故在無(wú)圈圖上，能級(jí)和匹配能級(jí)是一致的。自從2012年Gutman和Wagner在文[4]中提出圖的匹配能級(jí)的概念以來(lái)，對(duì)這個(gè)主題已經(jīng)有了大量的研究，文[4]中指出在所有n階圖中，匹配能級(jí)最小的是空?qǐng)D，最大的是完全圖, 也確定了匹配能級(jí)最小和最大的連通單圈圖。文[6-7]中確定了匹配能級(jí)最大和最小的連通雙圈圖。 文[8-9]中確定了匹配能級(jí)最大和最小的連通三圈圖。文[10]中確定了所有κ-連通圖中的匹配能級(jí)最大的圖和所有χ-色圖中匹配能級(jí)最大的圖等等。關(guān)于匹配數(shù)目的研究參見(jiàn)[11-13]。縱觀這些研究結(jié)果，主要都集中在對(duì)給定的一類(lèi)圖刻畫(huà)其匹配能級(jí)達(dá)到極值的圖，但很少有文獻(xiàn)對(duì)一類(lèi)圖的匹配能級(jí)給一個(gè)完全的排序，在這篇文章中，我們對(duì)一類(lèi)所謂的“8”字圖做這樣的工作，給出了點(diǎn)數(shù)相同的“8”字圖之間匹配能級(jí)的一個(gè)完全排序。作為推論，也給出這些圖的Hosoya指標(biāo)的一個(gè)完全排序。

以Pn，Cn，Kn分別表示n個(gè)點(diǎn)的路、圈和完全圖。以G∪H表示兩個(gè)圖G和H的并圖。 我們把形似“8”字的圖稱(chēng)為8-字圖，它是圈Ca+1上的一點(diǎn)和圈Cb+1上的一點(diǎn)粘結(jié)后得到的圖(見(jiàn)圖1)，記為記∞(a,b)。 顯然有∞(a,b)?∞(b,a)。在文中沒(méi)有說(shuō)明的記號(hào)和術(shù)語(yǔ)參見(jiàn)文[1]。

圖1 “8-”字圖∞(a,b)(a≥2,b≥2)Fig. 1 The 8-shape graphs ∞(a,b)(a≥2,b≥2)

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)，則

(ii)μ(G,x)=μ(Ge,x)-μ(G{u,v},x)。

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

μ(Ps+t)=μ(Ps)μ(Pt)-μ(Ps-1)μ(Pt-1)

證明由引理2(ii)，結(jié)論顯然成立。

引理4設(shè)Pn是n個(gè)點(diǎn)的路，k使下圖有意義的整數(shù)，則

μ(Ps)μ(Pt)-μ(Ps-k)μ(Pt+k)=

μ(Ps-1)μ(Pt-1)-μ(Ps-k-1)μ(Pt+k-1)

證明由引理3，μ(Ps+t)=μ(Ps)μ(Pt)-μ(Ps-1)μ(Pt-1)，μ(Ps+t)=μ(Ps-k)μ(Pt+k)-μ(Ps-k-1)μ(Pt+k-1)，兩式相減便得上式。

引理5[4]設(shè)G是一個(gè)圖，則

這里m(G,k)是G中的k-匹配的數(shù)目。

G1G2?ME(G1)

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

μ(G1)-μ(G2)=tμ(H),(t>0)

則

(i)n-m是一個(gè)偶數(shù)；

(ii) 如果n-m≡0(mod 4), 則ME(G1)>ME(G2)；

(iii) 如果n-m≡2(mod 4), 則ME(G1)

證明

(i)由于多項(xiàng)式μ(Gi,x)(i=1,2)中xn-(2k-1)的系數(shù)均為零，則多項(xiàng)式μ(G1,x)-μ(G2,x)中xn-(2k-1)的系數(shù)也為零。于是tμ(H)的首項(xiàng)txm必定是形如txn-2k，對(duì)某個(gè)整數(shù)k。 故n-2k=m。 則n-m是一個(gè)偶數(shù)。

(ii) 不妨設(shè)n=m+4k，

μ(G1)=xn-m(G1,1)xn-2+…+

m(G1,2k)xm-m(G1,2k+1)xm-2+…,

μ(G2)=xn-m(G2,1)xn-2+…+

m(G2,2k)xm-m(G2,2k+1)xm-2+…,

μ(H)=xm-m(H,1)xm-2+…

由于μ(G1)=μ(G2)+tμ(H),比較系數(shù)得

所以G1?G2故ME(G1)>ME(G2)。

(iii) 不妨設(shè)n=m+4k+2，

μ(G1)=xn-m(G1,1)xn-2+…-

m(G1,2k+1)xm+m(G1,2k+2)xm-2+…,

μ(G2)=xn-m(G2,1)xn-2+…-

m(G2,2k+1)xm+m(G2,2k+2)xm-2+…,

μ(H)=xm-m(H,1)xm-2+…

由于μ(G1)=μ(G2)+tμ(H),比較系數(shù)得

m(G1,s)=

所以G1G2，故ME(G1)

2 主要定理及證明

定理1 對(duì)“8-”字圖∞(a,n-a-1)(a≥2), 有

(i)當(dāng)n=4k, 則

ME(∞(3,4k-4))>ME(∞(5,4k-6))>…>ME(∞(2k-1,2k))=ME(∞(2k,2k-1))>ME(∞(2k-2,2k+1))>…>ME(∞(4,4k-5))>ME(∞(2,4k-3))

(ii)當(dāng)n=4k+1, 則

ME(∞(3,4k-3))>ME(∞(5,4k-5))>…>ME(∞(2k-1,2k+1))>ME(∞(2k,2k))>ME(∞(2k-2,2k+2))>…>ME(∞(4,4k-4))>ME(∞(2,4k-2))

(iii) 當(dāng)n=4k+2, 則

ME(∞(3,4k-2))>ME(∞(5,4k-4))>…>ME(∞(2k-1,2k+2))>ME(∞(2k,2k+1))>ME(∞(2k-2,2k+3))>…>ME(∞(4,4k-3))>ME(∞(2,4k-1))

(iv) 當(dāng)n=4k+3 則

ME(∞(3,4k-1))>ME(∞(5,4k-3))>…>ME(∞(2k-1,2k+3))>ME(∞(2k+1,2k+1))>ME(∞(2k,2k+2))>ME(∞(2k-2,2k+4))>…>ME(∞(4,4k-2))>ME(∞(2,4k))

證明

(i)證明分以下兩步：

第一步，證明對(duì)正整數(shù)3≤s≤k,有

ME(∞(2s-3,4k-2s+2))>

ME(∞(2s-1,4k-2s))

(1)

由引理2-4得，

μ(∞(2s-3,4k-2s+2))-

μ(∞(2s-1,4k-2s))=

xμ(P2s-3)μ(P4k-2s+2)-

2μ(P2s-4)μ(P4k-2s+2)-2μ(P2s-3)μ(P4k-2s+1)-

[xμ(P2s-1)μ(P4k-2s)-

2μ(P2s-2)μ(P4k-2s)-2μ(P2s-1)μ(P4k-2s-1)]=

x[μ(P2s-3)μ(P4k-2s+2)-μ(P2s-1)μ(P4k-2s)]+

2[μ(P2s-2)μ(P4k-2s)-μ(P2s-4)μ(P4k-2s+2)]+

2[μ(P2s-1)μ(P4k-2s-1)-μ(P2s-3)μ(P4k-2s+1)]=

x[μ(P4k-4s+5)-μ(P2)μ(P4k-4s+3)]+

2[μ(P2)μ(P4k-4s+4)-(P4k-4s+6)]+

2[μ(P2)μ(P4k-4s+2)-μ(P4k-4s+4)]=

-xμ(P1)μ(P4k-4s+2)+2μ(P1)μ(P4k-4s+3)+

2μ(P1)μ(P4k-4s+1)=

x2μ(P4k-4s+2)=μ(2K1∪P4k-4s+2)

因此，由引理6(ii) 得到不等式(1)。

第二步，證明對(duì)正整數(shù)2≤s≤k,有

ME(∞(2s,4k-2s-1))>

ME(∞(2s-2,4k-2s+1))

(2)

由引理2-4得，

μ(∞(2s,4k-2s-1))-

μ(∞(2s-2,4k-2s+1))=

xμ(P2s)μ(P4k-2s-1)-2μ(P2s-1)·

μ(P4k-2s-1)-2μ(P2s)μ(P4k-2s-2)-

[xμ(P2s-2)μ(P4k-2s+1)-2μ(P2s-3)μ(P4k-2s+1)-

2μ(P2s-2)μ(P4k-2s)]=

x[μ(P2s)μ(P4k-2s-1)-μ(P2s-2)μ(P4k-2s+1)]+

2[μ(P2s-3)μ(P4k-2s+1)-

μ(P2s-1)μ(P4k-2s-1)]+

2[μ(P2s-2)μ(P4k-2s)-μ(P2s)μ(P4k-2s-2)]=

x[μ(P2)μ(P4k-4s+1)-μ(P4k-4s+3)]+

2[(P4k-4s+4)-μ(P2)μ(P4k-4s+2)]+

2[μ(P4k-4s+2)-μ(P2)μ(P4k-4s)]=

xμ(P1)μ(P4k-4s)-2μ(P1)μ(P4k-4s+1)-

2μ(P1)μ(P4k-4s-1)=

-x2μ(P4k-4s)=-μ(2K1∪P4k-4s)

由引理6(iii)得到不等式(2)。

(ii) 證明分以下三步。

第一步，證明對(duì)正整數(shù)3≤s≤k,有

ME(∞(2s-3,4k-2s+3))>

ME(∞(2s-1,4k-2s+1))

(3)

與(i)的第一步類(lèi)似可得到，

μ(∞(2s-3,4k-2s+3))-

μ(∞(2s-1,4k-2s+1))=

μ(2K1∪P4k-4s+3)

由引理6(iii)得到不等式(3)。

第二步，證明不等式

ME(∞(2k-1,2k+1))>ME(∞(2k,2k))

(4)

μ(∞(2k-1,2k+1))-μ(∞(2k,2k))=

xμ(P2k-1)μ(P2k+1)-

2μ(P2k-2)μ(P2k+1)-2μ(P2k-1)μ(P2k)-

[xμ(P2k)μ(P2k)-2μ(P2k-1)μ(P2k)-

2μ(P2k)μ(P2k-1)]=

x[μ(P2k-1)μ(P2k+1)-μ(P2k)μ(P2k)]+

2[μ(P2k-1)μ(P2k)-μ(P2k-2)μ(P2k+1)]=

x[μ(P2)-μ(P1)μ(P1)]+

2[μ(P1)μ(P2)-μ(P3)]=μ(K1)

所以，由引理6(ii)得到不等式(4)。

第三步，證明對(duì)正整數(shù)2≤s≤k,有

ME(∞(2s,4k-2s))>

ME(∞(2s-2,4k-2s+2))

(5)

與(i)的第二步類(lèi)似可得到，

μ(∞(2s,4k-2s))-

μ(∞(2s-2,4k-2s+2))=

-μ(2K1∪P4k-4s+1)

由引理6(iii)得到不等式(5)。

(iii)、(iv)證明與(i)或(ii)類(lèi)似，略。

下面的兩個(gè)推論是定理1的直接推論。

推論1 設(shè)“8-”字圖∞(a,b)(a≥2,b≥2)滿足a+b+1=n，則它的Hosoya指標(biāo)排序?yàn)?/p>

(i) 當(dāng)n=4k, 則

Z(∞(3,4k-4))>Z(∞(5,4k-6))>…>

Z(∞(2k-1,2k))=Z(∞(2k,2k-1))>

Z(∞(2k-2,2k+1))>…>

Z(∞(4,4k-5))>Z(∞(2,4k-3))

(ii) 當(dāng)n=4k+1, 則

Z(∞(3,4k-3))>Z(∞(5,4k-5))>…>

Z(∞(2k-1,2k+1))>

Z(∞(2k,2k))>Z(∞(2k-2,2k+2))>…>

Z(∞(4,4k-4))>Z(∞(2,4k-2))

(iii) 當(dāng)n=4k+2, 則

Z(∞(3,4k-2))>Z(∞(5,4k-4))>…>

Z(∞(2k-1,2k+2))>

Z(∞(2k,2k+1))>Z(∞(2k-2,2k+3))>

…>Z(∞(4,4k-3))>Z(∞(2,4k-1))

(iv) 當(dāng)n=4k+3 則

Z(∞(3,4k-1))>Z(∞(5,4k-3))>

…>Z(∞(2k-1,2k+3))>

Z(∞(2k+1,2k+1))>Z(∞(2k,2k+2))>

Z(∞(2k-2,2k+4))>…>

Z(∞(4,4k-2))>Z(∞(2,4k))

推論2 在所有n個(gè)點(diǎn)的“8”-字圖中，∞(3,n-4)的匹配能級(jí)最大，∞(2,n-3)的匹配能級(jí)最小。類(lèi)似地，∞(3,n-4)的Hosoya指標(biāo)最大，∞(2,n-3)的Hosoya指標(biāo)最小。