一類雙圈圖的匹配能量和Hosoya指標排序

馬海成，李丹陽，解承玲

(青海民族大學數學與統計學院，青海 西寧 810007)

1 預備知識

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

這里m(G,k)是G中k-匹配的數目，且約定m(G,0)=1.為了方便，本文中將μ(G，x)簡記為μ(G).

定義1設λ1，λ2,…，λn是圖G的匹配多項式的所有根，定義它的匹配能量為

設G是一個圖，以V(G)和E(G)分別表示圖G的點集和邊集.如果e∈E(G),以Ge表示從圖G中刪去邊e后得到的圖.如果V1?V(G)，以GV1表示從圖G中刪去V1中的所有點以及和這些點關聯的所有邊后得到的圖.如果V1={u}，將G(〗u}簡記為Gu.以G∪H表示兩個圖G和H的并圖.以Pn，Cn，Kn分別表示n個點的路、圈和完全圖.路Ps+2的兩個端點分別與圈Ca+1和Cb+1上的一個點黏結后得到的連通圖稱為啞鈴圖(見圖1)，記為∞(a，s，b)，這里的s≥0,a≥2,b≥2.路Ps+1的一個端點與圈Ca+1上的一個點黏結后得到的a+s+1個點的連通圖稱為Q-圖，記為Q(a，s)，這里的s≥0,a≥2.以P(s，t)表示Ps∪Pt.文中沒有說明的記號和術語參見文獻[1].

圖1 啞鈴圖∞(a，s，b)Fig.1 The dumbbell shape graph ∞(a,s,b)

2 若干引理

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

EM(G)=2π∫+∞01x2ln[∑k≥0m(G,k)x2k]dx,

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

由引理5,規定一種偏序關系“?”.設G1和G2是兩個n階圖，對所有的非負整數k,若滿足m(G1，k)≤m(G2，k)，則定義G1?G2.若不等式m(G1，k)≤m(G2，k)對某個非負整數k是嚴格的，則定義G1G2.于是，由引理5可以得到下面的結果：

G1?G2?EM(G1)≤EM(G2),Z(G1)≤Z(G2)；

G1G2?EM(G1)

引理6[13]設G1和G2是兩個n階圖，如果存在一個m階圖H,滿足

μ(G1)-μ(G2)=μ(H),

則：

(i)n-m是一個偶數；

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

(iii) 如果n-m≡2(mod 4),則G1G2.

設H是一個m階的圖，f(x)是一個多項式(它未必是一個圖的匹配多項式)，如果f(x)與μ(H)有相同的形式，即

這里的ak≥0,且至少有一個ak>0,記f(x)≈μ(H).

眾所周知，對于圖G1和G2，多項式μ(G1)-μ(G2)一般不是一個圖的匹配多項式，但若存在一個m階的圖H,使得μ(G1)-μ(G2)≈μ(H)，則引理6的結論也成立，這就是下面的引理7.

引理7設G1和G2是兩個n階圖，且μ(G1)-μ(G2)≠0，如果存在一個m階圖H,滿足

μ(G1)-μ(G2)≈μ(H),

則：

(i)n-m是一個偶數；

(ii) 如果n-m≡0(mod 4)，則G1?G2；

(iii) 如果n-m≡2(mod 4)，則G1G2.

(ii) 不妨設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+…，

f(x)=a0xm-a1xm-2+….

由于μ(G1)=μ(G2)+f(x)，比較系數得

所以G1?G2.

(iii) 不妨設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-…，

f(x)=a0xm-a1xm-2+….

由于μ(G1)=μ(G2)+f(x),比較系數得

所以G1G2.

3 主要定理及證明

引理8(i) 設a≤b,則μ(Pa∪Q(b，s))-μ(Pa-2∪Q(b+2,s))=μ(P1∪Q(b-a+1,s))；

(ii) 設4≤a≤b,則μ(∞(a，s，b))-μ(∞(a-2,s,b+2))≈-μ(P1∪Q(b-a+2，s)).

證明(i) 由引理2(ii)，

μ(Q(b，s))=μ(Pb+s+1)-μ(Pb-1∪Ps)，

由引理4,

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

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

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

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

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

(ii) 由引理2(i)，

μ(∞(a，s，b))=xμ(Pa∪Q(b，s))-

2μ(Pa-1∪Q(b，s))-μ(Pa∪Q(b，s-1))，

μ(∞(a-2，s，b+2))=xμ(Pa-2∪Q(b+2，

s))-2μ(Pa-3∪Q(b+2，s))-

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

由(i)和引理2知，

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

x[μ(Pa∪Q(b，s))-μ(Pa-2∪Q(b+2,s))]-

2[μ(Pa-1∪Q(b,s))-μ(Pa-3∪Q(b+2,s))]-

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

s-1))]=xμ(P1∪Q(b-a+1,s))-

2μ(P1∪Q(b-a+2,s))-μ(P1∪Q(b-a+

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

2μ(P1∪Q(b-a+2,s))=μ(P1)[μ(Q(b-

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

μ(P1∪Q(b-a+2,s))=μ(P1)[(μ(Pb+s-a+3)-

μ(Pb-a∪Ps+1))-(μ(Pb+s-a+3)-

μ(Pb-a+1∪Ps))]-μ(P1∪Q(b-a+2,s))=

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

μ(P1∪Q(b-a+2，s)).

1) 若s≥b-a+1,由引理4知，μ(P(b-a+1,s))-μ(P(b-a,s+1))=μ(Ps-b+a-1)，則

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

μ(P1)[μ(Ps-b+a-1)-μ(Q(b-a+2，s)].

圖Q(b-a+2，s)的點數N=b-a+s+3,路Ps-b+a-1的點數N1=s-b+a-1,N-N1=2(b-a)+4,即從圖Q(b-a+2，s)中刪去一條路P2(b-a)+4后便得到路Ps-b+a-1.路P2(b-a)+4上有一個完美匹配(即飽和了所有點的匹配)，于是路Ps-b+a-1上的任何一個k匹配，并上路P2(b-a)+4的完美匹配后便得到圖Q(b-a+2，s)上的一個k+b-a+2匹配，故m(Ps-b+a-1，k)≤m(Q(b-a+2，s)，k+b-a+2).

由于

b-a+2)xN1-2k，

(1)

所以

μ(Q(b-a+2，s))-μ(Ps-b+a-1)=

a+2)-m(Ps-b+a-1,k)]xN1-2k.

(2)

結合不等式m(Ps-b+a-1,k)≤m(Q(b-a+2,s),k+b-a+2)),比較多項式μ(Q(b-a+2，s))-μ(Ps-b+a-1) 和多項式μ(Q(b-a+2，s))，即式(1)和式(2)，發現它們有完全一樣的形式.只是當b-a+2為偶數時，多項式μ(Q(b-a+2,s))-μ(Ps-b+a-1)中項xN1-2k的系數比多項式μ(Q(b-a+2,s))中項xN1-2k的系數的絕對值會減少，符號仍然與多項式μ(Q(b-a+2,s))的項xN1-2k符號相同；當b-a+2為奇數時，多項式μ(Q(b-a+2,s))-μ(Ps-b+a-1)中項xN1-2k的系數比多項式μ(Q(b-a+2，s))中項xN1-2k的系數的絕對值會增加，符號仍然與多項式μ(Q(b-a+2，s))的項xN1-2k符號相同.也就是說，μ(Q(b-a+2,s))-μ(Ps-b+a-1)≈μ(Q(b-a+2,s))，于是μ(∞(a,s,b))-μ(∞(a-2,s,b+2))≈-μ(P1∪Q(b-a+2,s)).

2) 若s=b-a,此時μ(P(b-a+1,s))-μ(P(b-a,s+1))=0，則μ(∞(a,s,b))-μ(∞(a-2,s,b+2))=-μ(P1)μ(Q(b-a+2,s).

3) 若s≤b-a-1,由引理4知，此時μ(P(b-a+1,s))-μ(P(b-a,s+1))=-μ(Pb-a-s-1)，則

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

μ(P1)[-μ(Pb-a-s-1) -μ(Q(b-a+2,s)].

圖Q(b-a+2，s)的點數N=b-a+s+3,路Pb-a-s-1的點數N2=b-a-s-1,N-N2=2s+4,即從圖Q(b-a+2,s)中刪去一條路P2s+4后便得到路Pb-a-s-1.路P2s+4上有一個完美匹配，于是路Pb-a-s-1上的任何一個k匹配，并上路P2s+4的完美匹配后便得到圖Q(b-a+2,s)上的一個k+s+2匹配，故m(Pb-a-s-1,k)≤m(Q(b-a+2,s),k+s+2).

由于

2)xN2-2k，

(3)

所以

μ(Q(b-a+2，s))+μ(Pb-a-s-1)=

2)+m(Pb-a-s-1,k)]xN2-2k.

(4)

結合不等式m(Pb-a-s-1，k)≤m(Q(b-a+2，s)，k+s+2),與1)類似，得到μ(Q(b-a+2,s)+μ(Pb-a-s-1)≈μ(Q(b-a+2,s),于是μ(∞(a，s,b))-μ(∞(a-2,s,b+2))≈-μ(P1∪Q(b-a+2,s)).

引理9(i)μ(P2k∪Q(2k,s))-μ(P2k-1∪Q(2k+1,s))=μ(Ps+1)；

(ii)μ(P2k-1∪Q(2k,s))-μ(P2k-2∪Q(2k+1,s))=μ(Ps+2)-μ(Ps)；

(iii)μ(∞(2k，s，2k))-μ(∞(2k-1,s,2k+1))≈-μ(Cs+2).

證明(i) 由引理2(ii),μ(P2k∪Q(2k,s))=μ(P2k∪P2k+s+1)-μ(P2k∪P2k-1∪Ps)，μ(P2k-1∪Q(2k+1,s))=μ(P2k-1∪P2k+s+2)-μ(P2k-1∪P2k∪Ps)，由引理4,μ(P2k∪Q(2k,s))-μ(P2k-1∪Q(2k+1,s))=μ(Ps+1).

(ii) 由引理2(ii)，μ(P2k-1∪Q(2k，s))=μ(P2k-1∪P2k+s+1)-μ(P2k-1∪P2k-1∪Ps)，μ(P2k-2∪Q(2k+1,s))=μ(P2k-2∪P2k+s+2)-μ(P2k-2∪P2k∪Ps)，由引理4,μ(P2k-1∪Q(2k,s))-μ(P2k-2∪Q(2k+1,s))=μ(Ps+2)-μ(Ps).

(iii) 由引理2(i)，μ(∞(2k，s，2k))=xμ(P2k∪Q(2k，s))-2μ(P2k-1∪Q(2k，s))-μ(P2k∪Q(2k,s-1)),μ(∞(2k-1,s,2k+1))=xμ(P2k-1∪Q(2k+1,s))-2μ(P2k-2∪Q(2k+1,s))-μ(P2k-1∪Q(2k+1,s-1)).

由(i)和(ii)知，μ(∞(2k，s，2k))-μ(∞(2k-1，s，2k+1))=xμ(Ps+1)-2(μ(Ps+2)-μ(Ps))-μ(Ps)=-μ(Ps+2)+2μ(Ps)=-μ(Cs+2)+μ(Ps).

圈Cs+2上刪去一個P2便得到路Ps,而P2有完美匹配，同引理8的證明類似，得到-μ(Cs+2)+μ(Ps)≈-μ(Cs+2).

引理10(i)μ(P2k+1∪Q(2k+1,s))-μ(P2k∪Q(2k+2,s))=μ(Ps+1)；

(ii)μ(P2k∪Q(2k+1,s))-μ(P2k-1∪Q(2k+2,s))=μ(Ps+2)-μ(Ps)；

(iii)μ(∞(2k+1,s, 2k+1))-μ(∞(2k，s,2k+2))≈-μ(Cs+2).

證明與引理9類似，略.

定理1設s是一個固定的非負整數，對圖∞(a，s，b),有：

(i) 當a+b=4k,∞(3，s, 4k-3)?∞(5，s,4k-5)?…?∞(2k-1,s,2k+1)?∞(2k，s,2k)?∞(2k-2,s,2k+2)?…?∞(4，s,4k-4)?∞(2，s,4k-2);

(ii) 當a+b=4k+1,∞(3，s,4k-2)?∞(5，s,4k-4)?…?∞(2k-1,s,2k+2)?∞(2k+1,s,2k)=∞(2k，s,2k+1)?∞(2k-2,s,2k+3)?…?∞(4，s,4k-3)?∞(2，s,4k-1);

(iii) 當a+b=4k+2,∞(3，s,4k-1)?∞(5，s,4k-3)?…?∞(2k-1,s,2k+3)?∞(2k+1,s,2k+1)?∞(2k，s,2k+2)?…?∞(4，s,4k-2)?∞(2，s,4k);

(iv) 當a+b=4k+3,∞(3，s,4k)?∞(5，s,4k-2)?…?∞(2k+1,s,2k+2)?∞(2k+3,s,2k)=∞(2k,s,2k+3)?∞(2k-2,s,2k+5)?…?∞(4,s,4k-1)?∞(2，s,4k+1).

證明由引理8(ii)，當4≤a≤b,有

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

-μ(P1∪Q(b-a+2,s)).

(5)

等式(5)左端的每個圖的點數為a+b+s+2,右端的圖的點數為b+s-a+4，它們的差為2a-2.于是由引理7知，當a為奇數時有∞(a-2，s，b+2))?∞(a，s，b)，當a為偶數時有∞(a-2，s，b+2))∞(a，s，b),由此便得到(i)～(iv)中的不等式的前半段和后半段.

由引理9(iii)知，

μ(∞(2k，s，2k))-μ(∞(2k-1,s,2k+1))≈

-μ(Cs+2).

(6)

等式(6)左端的每個圖的點數為4k+s+2,右端圖的點數為s+2,它們的差為4k.于是由引理7，得到定理1(i)中間的偏序關系∞(2k-1，s，2k+1)?∞(2k，s，2k).

類似地，由引理10(iii)知，

μ(∞(2k+1,s,2k+1))-μ(∞(2k，s，2k+2))≈

-μ(Cs+2).

(7)

等式(7)左端的每個圖的點數為4k+s+4,右端的圖的點數為s+2，它們的差為4k+2.于是由引理7，得到定理1(iii)中間的偏序關系∞(2k+1,s,2k+1)?∞(2k，s，2k+2).定理證畢.

下面的3個推論是定理1的直接推論.

推論1設s是一個固定的非負整數，對圖∞(a，s，b),有：

(i) 當a+b=4k,EM(∞(3,s，4k-3))>EM(∞(5,s,4k-5))> …>EM(∞(2k-1,s,2k+1))>EM(∞(2k，s，2k))>EM(∞(2k-2，s，2k+2))>…>EM(∞(4，s，4k-4))>EM(∞(2，s，4k-2));

(ii) 當a+b=4k+1，EM(∞(3，s，4k-2))>EM(∞(5，s，4k-4))>…>EM(∞(2k-1，s，2k+2))>EM(∞(2k+1，s，2k))=EM(∞(2k，s，2k+1))>EM(∞(2k-2，s，2k+3))>…>EM(∞(4，s，4k-3))>EM(∞(2，s，4k-1));

(iii) 當a+b=4k+2，EM(∞(3，s，4k-1))>EM(∞(5，s，4k-3))>…>EM(∞(2k-1，s，2k+3))>EM(∞(2k+1，s，2k+1))>EM(∞(2k，s，2k+2))>…>EM(∞(4，s，4k-2))>EM(∞(2，s，4k));

(iv) 當a+b=4k+3，EM(∞(3，s，4k))>EM(∞(5，s，4k-2))>…>EM(∞(2k+1，s，2k+2))>EM(∞(2k+3，s，2k))=EM(∞(2k，s，2k+3))>EM(∞(2k-2，s，2k+5))>…>EM(∞(4，s，4k-1))>EM(∞(2，s，4k+1)).

推論2設s是一個固定的非負整數，對圖∞(a，s，b),有：

(i) 當a+b=4k，Z(∞(3，s，4k-3))>Z(∞(5，s，4k-5))>…>Z(∞(2k-1，s，2k+1))>Z(∞(2k，s，2k))>Z(∞(2k-2，s，2k+2))>…>Z(∞(4，s，4k-4))>Z(∞(2，s，4k-2));

(ii) 當a+b=4k+1，Z(∞(3，s，4k-2))>Z(∞(5，s，4k-4))>…>Z(∞(2k-1，s，2k+2))>Z(∞(2k+1，s，2k))=Z(∞(2k，s，2k+1))>Z(∞(2k-2，s，2k+3))>…>Z(∞(4,s，4k-3))>Z(∞(2,s，4k-1));

(iii) 當a+b=4k+2，Z(∞(3，s，4k-1))>Z(∞(5，s，4k-3))>…>Z(∞(2k-1，s，2k+3))>Z(∞(2k+1，s，2k+1))>Z(∞(2k，s，2k+2))>…>Z(∞(4，s，4k-2))>Z(∞(2，s，4k));

(iv) 當a+b=4k+3,Z(∞(3,s，4k))>Z(∞(5,s，4k-2))>…>Z(∞(2k+1，s，2k+2))>Z(∞(2k+3，s，2k))=Z(∞(2k，s，2k+3))>Z(∞(2k-2，s，2k+5))>…>Z(∞(4,s,4k-1))>Z(∞(2,s,4k+1)).

推論3在s和a+b=c固定的啞鈴圖∞(a，s,b)圖中，匹配能量最大的圖是∞(3,s，c-3),最小的圖是∞(2,s，c-2);Hosoya指標最大的圖是∞(3,s，c-3),最小的圖是∞(2,s,c-2).

注3本文給出了啞鈴圖∞(a，s，b)在s不變而a和b兩個變量變化下匹配能量的全排序和Hosoya指標的全排序.如果讓3個變量a、s和b都變化，如何給出啞鈴圖∞(a，s，b)匹配能量的全排序將很復雜，有待進一步探討.