葛春雨

(蘭州交通大學(xué) 數(shù)理學(xué)院， 甘肅 蘭州 730070)

本文考慮的圖都是無(wú)向簡(jiǎn)單圖。設(shè)圖G的頂點(diǎn)集和邊集分別為V(G)={v1,v2,…,vn}和E(G)={e1,e2,…,em}。圖G的鄰接矩陣A(G)=(aij)n×n定義如下：若頂點(diǎn)vi與頂點(diǎn)vj鄰接，則aij=1;否則aij=0。度對(duì)角矩陣D(G)=diag(d(v1),d(v2),…,d(vn))，其中d(vi)為頂點(diǎn)vi的度。圖G的無(wú)符號(hào)拉普拉斯矩陣Q(G)=D(G)+A(G)。設(shè)|E(G)|=m，圖G的關(guān)聯(lián)矩陣I(G)=(bij)n×m，當(dāng)頂點(diǎn)vi是邊ej的端點(diǎn)時(shí)，bij=1；否則bij=0。圖G的關(guān)聯(lián)能量[1]IE(G)是指關(guān)聯(lián)矩陣I(G)的奇異值之和。Gutman等[2]指出圖G的關(guān)聯(lián)能量等于其所有無(wú)符號(hào)拉普拉斯特征值的平方根之和。

圖G的無(wú)符號(hào)拉普拉斯特征多項(xiàng)式定義為

其中φi(G)為圖G的無(wú)符號(hào)拉普拉斯多項(xiàng)式系數(shù)。

令Gn是包含所有n個(gè)頂點(diǎn)簡(jiǎn)單圖的集合。令?是Gn上通過(guò)比較任意兩個(gè)圖的無(wú)符號(hào)拉普拉斯系數(shù)的大小所定義的偏序關(guān)系。對(duì)任意兩個(gè)圖G，H∈Gn,如果φi(G)≤φi(H)對(duì)所有的i=1,2,…,n成立，那么我們稱G?H；若存在一個(gè)值i使得滿足φi(G)<φi(H)，則稱GH。

文獻(xiàn)[3]證明了所有n個(gè)頂點(diǎn)的單圈圖構(gòu)成的集合關(guān)于偏序?有兩個(gè)極大元和兩個(gè)極小元；Mirzakhah和Kiani[4]研究了單圈圖的無(wú)符號(hào)拉普拉斯矩陣的系數(shù)，得到了n個(gè)頂點(diǎn)的單圈圖恰有兩個(gè)極小元和極大元；文獻(xiàn)[5]討論了所有n個(gè)頂點(diǎn)的雙圈圖構(gòu)成的集合關(guān)于偏序關(guān)系?的極小元；文獻(xiàn)[6]刻畫(huà)了所有頂點(diǎn)數(shù)為n、匹配數(shù)為m的單圈圖的集合關(guān)于偏序關(guān)系?的極小元；文獻(xiàn)[7]刻畫(huà)了n個(gè)頂點(diǎn)不含偶圈的連通圖集合關(guān)于偏序關(guān)系?的極小元；更多關(guān)于單圈圖的研究可參考文獻(xiàn)[8-11]。受上述文獻(xiàn)啟發(fā)，本文主要研究具有完美匹配的單圈圖的無(wú)符號(hào)拉普拉斯系數(shù)及其極圖。

1 單圈圖的無(wú)符號(hào)拉普拉斯系數(shù)

圖1 G和

圖2 G和

圖3 G和G′

其中求和項(xiàng)取遍G的所有恰有i條邊的TU-子圖Hi。顯然φ0(G)=1,φ1(G)=2m。

引理2[5]令G是一個(gè)n≥4個(gè)頂點(diǎn)的簡(jiǎn)單連通圖。如果Gμv是由G通過(guò)α-變換[13]得到的，那么Gμv?G，即

φi(Gμv)≤φi(G),i=0,1,…,n,

等號(hào)成立當(dāng)且僅當(dāng)或者i∈{0,1,n}且G是非二部圖，或者i∈{0,1,n-1,n}且G是二部圖。

等號(hào)成立當(dāng)且僅當(dāng)i∈{0,1,n}。

等號(hào)成立當(dāng)且僅當(dāng)i∈{0,1,n}。

等號(hào)成立當(dāng)且僅當(dāng)i∈{0,1}。

f:H ′→H,H′→H=f(H′),

其中

V(H)=V(H′),

{μ1μ3|μ1μ3∈E(H′)}+{μ2μ3|μ1μ3∈E(H′)},

則f:H ′→H是單射。令N是H′中的不含頂點(diǎn)μ1、μ2的所有連通分支的權(quán)重。除了H′中包含μ1和μ2的分支，H′中其他任意一個(gè)分支對(duì)應(yīng)H中的一些分支。分以下3種情形討論。

情形1 若μ1μ2∈E(H′)，則H′和H除了R′和f(R′)外有相同的連通分支，而且兩個(gè)連通分支R′和f(R′)有相同的階數(shù)，因此W(H)=W(H′)。

情形2 若μ1μ2E(H′)，并且μ1包含在H′的一個(gè)奇單圈分支U′中，則H′中的兩個(gè)分支{μ2}和R′對(duì)應(yīng)著H中的一個(gè)樹(shù)分支，通過(guò)單射f，得到H中樹(shù)分支階數(shù)至少為g。因此

W(H)-W(H′)≥g·N-4·1·N=N(g-4)≥0。

情形3 若μ1μ2E(H′)，且T′是H′的一棵樹(shù)。則H′和H除了R′和{μ2}外有相同的連通分支。定義通過(guò)單射f，H中有一個(gè)階數(shù)為a+1階的樹(shù)分支對(duì)應(yīng)于H′中階數(shù)為a+b+1的分支T′，且H中有一個(gè)階數(shù)為b+1階的樹(shù)分支對(duì)應(yīng)于H′中的分支{μ2}。因此

W(H)-W(H′)=(a+1)·(b+1)·N-(a+b+1)·N=Nab≥0,

等號(hào)成立當(dāng)且僅當(dāng)a=0或b=0。由以上討論和引理1知，當(dāng)2≤i≤n，有

等號(hào)成立當(dāng)且僅當(dāng)i∈{0,1}。

f:H ′→H,H′→H=f(H′),

其中

V(H)=V(H′),

則f:H ′→H是單射。令N是H′中的不含頂點(diǎn)μ1、μ2的所有連通分支的權(quán)重。我們假設(shè)在包含μ1的連通分支H-μ1μ2-μ1v1有a1+1個(gè)頂點(diǎn)，在包含μ2的連通分支H-μ1μ2-μ2μ3-μ2v2有a2+1個(gè)頂點(diǎn)，且a1,a2≥0。

若μ1、μ2在H′的一個(gè)分支R′中。注意到H′中的一個(gè)分支R′對(duì)應(yīng)著H=f(H′)中的一個(gè)分支f(R′)包含μ1；并且R′和f(R′)是樹(shù)分支或奇單圈分支時(shí)有相同的階數(shù)；同時(shí)除了H′中的一個(gè)分支R′，H′中的任意分支對(duì)應(yīng)著H中的一些分支。因此W(H)=W(H′)。

若μ1、μ2在H′中的兩個(gè)分支中，分以下兩種情形討論。

情形1R′是H′中的一棵樹(shù)，類似于定理1的證明可得W(H)-W(H′)≥0。

情形2R′是H′的一個(gè)奇單圈分支，假設(shè)|V(R′)V(Cg-1)|=λ(λ≥0)。

定義H1={H′∈H ′|R′是一個(gè)奇單圈分支，且μ1、μ2、μ3在2或3個(gè)分支中}。

子情形2.1μ1v1E(H′),μ2v2E(H′)。

H′中的4個(gè)分支R′、{v1}、{μ2}和{v2}對(duì)應(yīng)H=f(H′)的一個(gè)樹(shù)分支R1(含μ1、μ2,且|R1|≥g)及{v1}和{v2}，且H′和H除了這7個(gè)分支外有相同的分支，則

W(H)-W(H′)=(g+λ)·N-4·1·1·1·N≥N(g-4)≥0。

類似地，當(dāng)μ1v1∈E(H′),μ2v2∈E(H′)；μ1v1∈E(H′),μ2v2E(H′);μ1v1E(H′),μ2v2∈E(H′)時(shí),通過(guò)與子情形2.1相同的分析，有W(H)-W(H′)≥0。

綜上所述并結(jié)合引理1可得，當(dāng)2≤i≤n時(shí)，

令Gg(s1,t1;s2,t2;…;sg,tg)是一個(gè)n個(gè)頂點(diǎn)的單圈圖，它是在圈Cg:μ1μ2…μi…μgμ1的頂點(diǎn)μi(i=1,2,…,g)上連接si條長(zhǎng)為2的懸掛路和ti條懸掛邊得到的圖。

定理3 (1)G3(s1,1;s2,1;s3,1)G3(s1+s2+s3,1;0,1;0,1),n≥6;

(2)G3(s1,1;s2,0;s3,0)G3(s1+s2+s3,1;0,0;0,0),n≥4;

(3)G3(s1,1;s2,0;s3,0)G3(0,1;0,0;s1+s2+s3,0),n≥4;

(4)G4(s1,0;s2,0;s3,0;s4,0)G4(s1+s2+s3+s4,0;0,0;0,0;0,0),n≥4;

(5)G4(s1,1;s2,1;s3,1;s4,1)G4(s1+s2+s3+s4,1;0,1;0,1;0,1),n≥8;

(6)G4(s1,1;s2,1;s3,0;s4,0)G4(s1+s2+s3+s4,1;0,1;0,0;0,0),n≥6;

(7)G4(s1,0;s2,1;s3,1;s4,0)G4(s1+s2+s3+s4,0;0,1;0,1;0,0),n≥6。

證明下面僅證定理3中的(4)，其余各款的證明與(4)的證明類似，這里不再贅述。

令G′=G4(s1+s2+s3+s4,0;0,0;0,0;0,0)是由G=G4(s1,0;s2,0;s3,0;s4,0)通過(guò)γ-變換所得到的圖(如圖3所示)。要證GG′，僅需證φi(G)≥φi(G′)，對(duì)所有的i=0,1,…,n等號(hào)成立。顯然i∈{0,1,n}時(shí)，φi(G)=φi(G′)。下面假設(shè)2≤i≤n-1。令H ′和H分別是G′和G的恰有i條邊的TU-子圖的集合。顯然H ′和H中沒(méi)有奇單圈分支。令H ′=H′(1)∪H′(2)∪H′(3)∪H′(4),其中H′(j)(j=1,2,3,4)是μ1,μ2,μ3,μ4屬于j個(gè)不同分支的TU-子圖。

對(duì)任意的TU-子圖H′∈H ′，記R′是H′的含μ1的連通分支。令

f:H ′→H,H′→H=f(H′),

其中

V(H)=V(H′),

E(H)=E(H′)-{μ1x|x∈NR′(μ1)∩NG(μ2)}-{μ1x|x∈NR′(μ1)∩NG(μ4)}-

{μ1x|x∈NR′(μ1)∩NG(μ3){μ2,μ4}}+{μ2x|x∈NR′(μ1)∩(NG(μ2)}+

{μ4x|x∈NR′(μ1)∩NG(μ4)}+{μ3x|x∈NR′(μ1)∩NG(μ3){μ2,μ4}},

令N是H′中不含{μ1,μ2,μ3,μ4}所有分支的權(quán)重。記μ1μ2=e1,μ2μ3=e2,μ3μ4=e3,μ4μ1=e4。下面分4種情形分別討論。

情形1H′∈H′(1)，如果e1、e2、e3、e4中至少有3條邊屬于E(H′)，那么μ1、μ2、μ3、μ4在一個(gè)分支中，則W(H)=W(H′)，即

情形2H′∈H′(4)，若e1、e2、e3、e4?E(H′)，則μ1、μ2、μ3、μ4在4棵樹(shù)中，則W(H)-W(H′)=N[ab(cd+c+d+1)+ac(d+1)+ad+bc(d+1)+bd+cd]≥0,即

情形3H′∈H′(3)，若μ1、μ2、μ3、μ4在3棵樹(shù)中，則W(H)-W(H′)=[(a+b+2)(c+1)(d+1)+(a+d+2)(b+1)(c+1)+(a+1)(b+1)(c+d+2)+(a+1)(d+1)(b+c+2)-6(a+b+c+d+2)]N≥0,即

情形4H′∈H′(2)，若μ1、μ2、μ3、μ4在2棵樹(shù)中，則W(H)-W(H′)=[b(a+c+d+2)+d(a+b+c+2)+c(a+b+d+2)+a(b+c+d+2)+(a+b)(c+d)+(a+d)(b+c)]N≥0,從而

因此不等式φi(G)≥φi(G′)對(duì)所有i=0,1,2,…,n-1,n均成立。

Mirzakhah和Kiani在文獻(xiàn)[4]中建立了圖的關(guān)聯(lián)能量與無(wú)符號(hào)拉普拉斯系數(shù)之間的關(guān)系如下：

引理5[4]令G和H是n個(gè)頂點(diǎn)的兩個(gè)圖，若G?H,則IE(G)≤IE(H)，若GH,則IE(G)

3 總結(jié)

本文主要通過(guò)比較圖的無(wú)符號(hào)拉普拉斯系數(shù)的大小，借助幾種可以保持偏序關(guān)系?的圖變換，確定了具有完美匹配的單圈圖集中關(guān)于偏序關(guān)系的極小元和具有最小關(guān)聯(lián)能量的極值圖。