葛春雨
(蘭州交通大學(xué) 數(shù)理學(xué)院, 甘肅 蘭州 730070)
本文考慮的圖都是無向簡單圖。設(shè)圖G的頂點集和邊集分別為V(G)={v1,v2,…,vn}和E(G)={e1,e2,…,em}。圖G的鄰接矩陣A(G)=(aij)n×n定義如下:若頂點vi與頂點vj鄰接,則aij=1;否則aij=0。度對角矩陣D(G)=diag(d(v1),d(v2),…,d(vn)),其中d(vi)為頂點vi的度。圖G的無符號拉普拉斯矩陣Q(G)=D(G)+A(G)。設(shè)|E(G)|=m,圖G的關(guān)聯(lián)矩陣I(G)=(bij)n×m,當(dāng)頂點vi是邊ej的端點時,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)能量等于其所有無符號拉普拉斯特征值的平方根之和。
圖G的無符號拉普拉斯特征多項式定義為
其中φi(G)為圖G的無符號拉普拉斯多項式系數(shù)。
令Gn是包含所有n個頂點簡單圖的集合。令?是Gn上通過比較任意兩個圖的無符號拉普拉斯系數(shù)的大小所定義的偏序關(guān)系。對任意兩個圖G,H∈Gn,如果φi(G)≤φi(H)對所有的i=1,2,…,n成立,那么我們稱G?H;若存在一個值i使得滿足φi(G)<φi(H),則稱GH。
文獻(xiàn)[3]證明了所有n個頂點的單圈圖構(gòu)成的集合關(guān)于偏序?有兩個極大元和兩個極小元;Mirzakhah和Kiani[4]研究了單圈圖的無符號拉普拉斯矩陣的系數(shù),得到了n個頂點的單圈圖恰有兩個極小元和極大元;文獻(xiàn)[5]討論了所有n個頂點的雙圈圖構(gòu)成的集合關(guān)于偏序關(guān)系?的極小元;文獻(xiàn)[6]刻畫了所有頂點數(shù)為n、匹配數(shù)為m的單圈圖的集合關(guān)于偏序關(guān)系?的極小元;文獻(xiàn)[7]刻畫了n個頂點不含偶圈的連通圖集合關(guān)于偏序關(guān)系?的極小元;更多關(guān)于單圈圖的研究可參考文獻(xiàn)[8-11]。受上述文獻(xiàn)啟發(fā),本文主要研究具有完美匹配的單圈圖的無符號拉普拉斯系數(shù)及其極圖。
圖1 G和
圖2 G和
圖3 G和G′
其中求和項取遍G的所有恰有i條邊的TU-子圖Hi。顯然φ0(G)=1,φ1(G)=2m。
引理2[5]令G是一個n≥4個頂點的簡單連通圖。如果Gμv是由G通過α-變換[13]得到的,那么Gμv?G,即
φi(Gμv)≤φi(G),i=0,1,…,n,
等號成立當(dāng)且僅當(dāng)或者i∈{0,1,n}且G是非二部圖,或者i∈{0,1,n-1,n}且G是二部圖。
等號成立當(dāng)且僅當(dāng)i∈{0,1,n}。
等號成立當(dāng)且僅當(dāng)i∈{0,1,n}。
等號成立當(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′中的不含頂點μ1、μ2的所有連通分支的權(quán)重。除了H′中包含μ1和μ2的分支,H′中其他任意一個分支對應(yīng)H中的一些分支。分以下3種情形討論。
情形1 若μ1μ2∈E(H′),則H′和H除了R′和f(R′)外有相同的連通分支,而且兩個連通分支R′和f(R′)有相同的階數(shù),因此W(H)=W(H′)。
情形2 若μ1μ2E(H′),并且μ1包含在H′的一個奇單圈分支U′中,則H′中的兩個分支{μ2}和R′對應(yīng)著H中的一個樹分支,通過單射f,得到H中樹分支階數(shù)至少為g。因此
W(H)-W(H′)≥g·N-4·1·N=N(g-4)≥0。
情形3 若μ1μ2E(H′),且T′是H′的一棵樹。則H′和H除了R′和{μ2}外有相同的連通分支。定義通過單射f,H中有一個階數(shù)為a+1階的樹分支對應(yīng)于H′中階數(shù)為a+b+1的分支T′,且H中有一個階數(shù)為b+1階的樹分支對應(yīng)于H′中的分支{μ2}。因此
W(H)-W(H′)=(a+1)·(b+1)·N-(a+b+1)·N=Nab≥0,
等號成立當(dāng)且僅當(dāng)a=0或b=0。由以上討論和引理1知,當(dāng)2≤i≤n,有
等號成立當(dāng)且僅當(dāng)i∈{0,1}。
f:H ′→H,H′→H=f(H′),
其中
V(H)=V(H′),
則f:H ′→H是單射。令N是H′中的不含頂點μ1、μ2的所有連通分支的權(quán)重。我們假設(shè)在包含μ1的連通分支H-μ1μ2-μ1v1有a1+1個頂點,在包含μ2的連通分支H-μ1μ2-μ2μ3-μ2v2有a2+1個頂點,且a1,a2≥0。
若μ1、μ2在H′的一個分支R′中。注意到H′中的一個分支R′對應(yīng)著H=f(H′)中的一個分支f(R′)包含μ1;并且R′和f(R′)是樹分支或奇單圈分支時有相同的階數(shù);同時除了H′中的一個分支R′,H′中的任意分支對應(yīng)著H中的一些分支。因此W(H)=W(H′)。
若μ1、μ2在H′中的兩個分支中,分以下兩種情形討論。
情形1R′是H′中的一棵樹,類似于定理1的證明可得W(H)-W(H′)≥0。
情形2R′是H′的一個奇單圈分支,假設(shè)|V(R′)V(Cg-1)|=λ(λ≥0)。
定義H1={H′∈H ′|R′是一個奇單圈分支,且μ1、μ2、μ3在2或3個分支中}。
子情形2.1μ1v1E(H′),μ2v2E(H′)。
H′中的4個分支R′、{v1}、{μ2}和{v2}對應(yīng)H=f(H′)的一個樹分支R1(含μ1、μ2,且|R1|≥g)及{v1}和{v2},且H′和H除了這7個分支外有相同的分支,則
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′)時,通過與子情形2.1相同的分析,有W(H)-W(H′)≥0。
綜上所述并結(jié)合引理1可得,當(dāng)2≤i≤n時,
令Gg(s1,t1;s2,t2;…;sg,tg)是一個n個頂點的單圈圖,它是在圈Cg:μ1μ2…μi…μgμ1的頂點μi(i=1,2,…,g)上連接si條長為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)通過γ-變換所得到的圖(如圖3所示)。要證GG′,僅需證φi(G)≥φi(G′),對所有的i=0,1,…,n等號成立。顯然i∈{0,1,n}時,φi(G)=φi(G′)。下面假設(shè)2≤i≤n-1。令H ′和H分別是G′和G的恰有i條邊的TU-子圖的集合。顯然H ′和H中沒有奇單圈分支。令H ′=H′(1)∪H′(2)∪H′(3)∪H′(4),其中H′(j)(j=1,2,3,4)是μ1,μ2,μ3,μ4屬于j個不同分支的TU-子圖。
對任意的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在一個分支中,則W(H)=W(H′),即
情形2H′∈H′(4),若e1、e2、e3、e4?E(H′),則μ1、μ2、μ3、μ4在4棵樹中,則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棵樹中,則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棵樹中,則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′)對所有i=0,1,2,…,n-1,n均成立。
Mirzakhah和Kiani在文獻(xiàn)[4]中建立了圖的關(guān)聯(lián)能量與無符號拉普拉斯系數(shù)之間的關(guān)系如下:
引理5[4]令G和H是n個頂點的兩個圖,若G?H,則IE(G)≤IE(H),若GH,則IE(G) 本文主要通過比較圖的無符號拉普拉斯系數(shù)的大小,借助幾種可以保持偏序關(guān)系?的圖變換,確定了具有完美匹配的單圈圖集中關(guān)于偏序關(guān)系的極小元和具有最小關(guān)聯(lián)能量的極值圖。3 總結(jié)