邱瑋（福州外語(yǔ)外貿(mào)學(xué)院　經(jīng)濟(jì)學(xué)院，福建　福州　350202）

圖的無(wú)符號(hào)Laplace特征多項(xiàng)式的系數(shù)

邱瑋
（福州外語(yǔ)外貿(mào)學(xué)院經(jīng)濟(jì)學(xué)院，福建福州350202）

摘要：我們考慮一般的連通圖G的Laplace特征多項(xiàng)式f(G；x)與它的剖分圖S(G)的特征多項(xiàng)式h(S(G)；x)之間會(huì)有什么關(guān)系，發(fā)現(xiàn)這兩個(gè)多項(xiàng)式的系數(shù)是否以及何時(shí)存在差別，并刻畫系數(shù)差的表達(dá)式．研究過(guò)程中，我們發(fā)現(xiàn)圖G的無(wú)符號(hào)Laplace特征多項(xiàng)式g(G；x)是一個(gè)重要的橋梁．于是我們對(duì)其系數(shù)也進(jìn)行研究，得到另一種新的方法證明圖的無(wú)符號(hào)Laplace特征多項(xiàng)式系數(shù)的組合解釋.

關(guān)鍵詞：剖分圖；一級(jí)半子圖；Laplace特征多項(xiàng)式；無(wú)符號(hào)Laplace特征多項(xiàng)式

1　背景介紹

設(shè)G是b個(gè)頂點(diǎn)m條邊的連通簡(jiǎn)單圖，A（G)，B（G)和D （G)分別是G的鄰接矩陣，關(guān)聯(lián)矩陣和度對(duì)角矩陣，Q（G)=D （G)-A（G)是G的Laplace矩陣，Q（G)=D（G)+A（G)是G的無(wú)符號(hào)Laplace矩陣.

用f（G;x)表示圖G的Laplace特征多項(xiàng)式，即

定理1.1[1，2]ai（G)=∑P（F)，i=0，1，…，n，這里求和取遍G的所有i條邊的子森林F，其中P（F)表示F的每個(gè)分支的頂點(diǎn)數(shù)的乘積.

用g（G;x)表示圖G的無(wú)符號(hào)Laplace特征多項(xiàng)式，即

給出圖的TU-子圖的定義：G的每個(gè)分支是樹或者是非偶單圈圖的生成子圖稱為G的TU-子圖.

定理1.2[3]bi（G)=∑Φ（H)，i=0，1，…，n，這里求和取遍G的所有i條邊的TU-子圖H，其中Φ（H)=4'∏si=0ni，H有c=s+t個(gè)分支T1，T2，…，Ts，U1，U2，…，Ut，其中Ti（1≤i≤s)是ni個(gè)頂點(diǎn)的樹，Uj（1≤j≤t)是非偶單圈圖.

定理1.3[4]對(duì)任意n個(gè)頂點(diǎn)的連通圖G，ai（G)≤bi（G)，i=0，1，…，n，等式成立當(dāng)且僅當(dāng)G是偶圖.

設(shè)G1是G的一個(gè)子圖，分別用r（G1)和s（G1)表示G1的秩和補(bǔ)秩，則有r（G1)=|V（G1)|-c（G1)，s（G1)=|E（G1)|-|V（G1)|+c（G1)，其中c（G1)是G1的連通分支數(shù).

G的子圖Λ稱為G的一級(jí)半子圖（elementary subgraph），如果Λ的每一個(gè)分支是一條邊或者是一個(gè)圈.若Λ是G的一級(jí)半子圖，則s（Λ)等于Λ的圈數(shù).若H是G的TU-子圖，則s（H)等于H的非偶單圈圖的分支數(shù).

用h（G;x)表示圖G的特征多項(xiàng)式，即

引理1.4[2]ci（G)=∑（-1)r（Λ)2s（Λ)，i=0，1，…，n，這里求和取遍G的所有i個(gè)頂點(diǎn)的一級(jí)半子圖Λ.

圖G的剖分圖S（G)為在G的每條邊e上插入一個(gè)新頂點(diǎn)所得到的圖.關(guān)于偶圖G的Laplace特征多項(xiàng)式與它的剖分圖S（G)的特征多項(xiàng)式之間的關(guān)系，Zhou和Gutman得到了下面的結(jié)果：

定理1.5[5]設(shè)G是n個(gè)頂點(diǎn)m條邊的偶圖，S（G)是它的剖分圖.則h（S（G);x)=xm-nf（G;x2).

2　定理1.2的證明

得S（G)的特征多項(xiàng)式為：

=xm-ndet（x2In-B（G)B（G)T)=xm-ndet（x2In-D（G)-A（G))

=xm-ng（G;x2)

注意到當(dāng)G是偶圖時(shí)，det（x2In-D（G)-A（G))=det（x2In-D（G) +A（G))，于是h（S（G);x)=xm-nf（G;x2).

現(xiàn)在設(shè)G是一般連通圖，研究h（S（G);x)與f（G;x2)系數(shù)的關(guān)系，實(shí)際上就是發(fā)現(xiàn)f（G;x)系數(shù)ai（G)與g（G;x)系數(shù)bi（G)的差別.對(duì)于bi（G)，以下用一種新的方法來(lái)證明它的組合解釋，即定理1.2內(nèi)容.

我們發(fā)現(xiàn)

注意到S（G)沒(méi)有奇圈，于是

由引理1.4，得到下列引理.

引理2.1（-1)ibi（G)=c2i（S（G))=∑（-1)r（Λ)2s（Λ)，i=0，1，…，n，這里求和取遍S（G)的所有2i個(gè)頂點(diǎn)的一級(jí)半子圖Λ.

為了闡明結(jié)論，先引入下面記號(hào).

定義G的子圖Λ'如下：收縮圈Ci的所有剖分點(diǎn)得到G的一個(gè)|V（Ci)|/2個(gè)頂點(diǎn)的圈，記為Ci'.設(shè)EΛ=E（C1')∪E（C2')∪…∪E（Cp')∪｛euk|k=1，2，…，q｝，則EΛ是G的邊集E（G)的子集.定義Λ'是G的由EΛ導(dǎo)出的子圖.設(shè)T1，T2，…，Ts，H1，H2，…，Ht是Λ'的分支，其中Tj（1≤j≤s)是樹而Hj（1≤j≤t)至少包含一個(gè)圈.顯然，|E（Tj)|≥1且|E（Hj)|≥3.

下面給出的結(jié)論是定理1.2證明的重要基礎(chǔ).

結(jié)論1 Λ'有i條邊.

結(jié)論2 Λ是S（Λ')的一級(jí)半子圖.特別地，Λ恰好含有S（Λ')中的i個(gè)v-型頂點(diǎn)和i個(gè)e-型頂點(diǎn).

結(jié)論3 Λ'的每個(gè)分支或者是樹或者是單圈圖，即Hj（1≤j≤t)是單圈圖.

由結(jié)論1和結(jié)論2，對(duì)于j=1，2，…，t，Λ恰好包含S（Hj)中的|E（Hj)|個(gè)v-型頂點(diǎn)和|E（Hj)|個(gè)e-型頂點(diǎn).又因?yàn)閨E（Hj)| ≤|V（Hj)|，于是|E（Hj)|=|V（Hj)|，即Hj（1≤j≤t)是單圈圖.結(jié)論3成立.

再由結(jié)論3，每個(gè)Hj恰好包含一個(gè)圈.設(shè)Cj是S（Hj)的圈，那么Cj有兩個(gè)完美匹配，記為M1（Cj)和M2（Cj).于是Cj恰有三組V（Cj)個(gè)頂點(diǎn)的一級(jí)半子圖：M1（Cj)，M2（Cj)和Cj.不難說(shuō)明S（Hj)-Cj恰有一個(gè)完美匹配，記為M（S（Hj)-Cj).這意味著下面結(jié)論.

結(jié)論4對(duì)于1≤j≤t，S（Hj)恰有三組V（S（Hj))個(gè)頂點(diǎn)的一級(jí)半子圖：M1（Cj)∪M（S（Hj)-Cj)，M2（Cj)∪M（S（Hj)-Cj)和Cj∪M （S（Hj)-Cj).

結(jié)論5設(shè)Λ1是S（Λ')的2i個(gè)頂點(diǎn)的一級(jí)半子圖.則Λ1可表示成M1∪M2∪…∪Ms∪M'1∪M'2∪…∪M't的形式，其中Mj（1≤j≤s)是S（Tj)的|E（Tj)|條邊的匹配，而M'j（1≤j≤t)是S（Hj)的V（S（Hj))個(gè)頂點(diǎn)的一級(jí)半子圖.

引理2.2[6]設(shè)T是樹，則它的剖分圖S（T)有|V（T)|個(gè)|E （T)|條邊的匹配.

由結(jié)論5和引理2.2，我們得到

結(jié)論7對(duì)任意Λk∈Γ（Λ')，Λk'=Λ'.

引理2.3設(shè)T1，T2，…，Ts，H1，H2，…，Ht是Λ'的分支，其中Tj（1≤j≤s)是樹，Hj（1≤j≤t)是單圈圖.假設(shè)H1，…，Hx是非偶單圈圖而Hx，…，Hx+y（x+y=t)是偶單圈圖，則

證明設(shè)Cj（1≤j≤t)是S（Hj)的圈.那么當(dāng)1≤j≤x時(shí)，|V （Cj)|=2（mod4)，而當(dāng)x+1≤j≤x+y=t時(shí)，|V（Cj)|=0（mod4).注意到Γ（Λ')是S（Λ')的2i個(gè)頂點(diǎn)的一級(jí)半子圖的集合，且它們都能被看成是S（G)的2i個(gè)頂點(diǎn)的一級(jí)半子圖.

記

M'j1=M1（Cj)∪M（S（Hj)-Cj)，M'j2=M2（Cj)∪M（S（Hj)-Cj)，

M'j3=Cj∪M（S（Hj)-Cj).

對(duì)于1≤kj≤3，j=1，2，…，t，定義Γk1k2…kt（Λ')是其元素形如M1∪M2∪…∪Ms∪M'1k1∪M'2k2，∪…∪M'tkt的集合，顯然有下列結(jié)論.

（2）若（k1，k2，…，kt)≠（l1，l2，…，lt)（kj，lj=1，2，3，1≤j≤t)，則Γ

（3）設(shè)Λ=M1∪M2∪…∪Ms∪M'1k1∪M'2k2，∪…∪M'tkt∈Γk1k2…kt（Λ').

如果在集合{k1，k2，…，kx}（{kx+1，kx+2，…，kt})中恰有x1（y1）個(gè)元素等于3，則Λ的分支數(shù)

所以（-1)r（Λ)2s（Λ)=（-1)c（Λ)2x1+y1=（-1)i+y12x1+y1.再由（1），（2）和（3）

定理1.2的新的證明：設(shè)Γ'（G)={Λ'1，Λ'2，…，Λ'ω}是G的i條邊的每個(gè)分支是樹或單圈圖的子圖的集合.再設(shè)Γ（Λ'j) （j=1，2，…，ω)是S（Λj)的2i個(gè)頂點(diǎn)的一級(jí)半子圖的集合，它們都可以看成是S（G)的一級(jí)半子圖.不難發(fā)現(xiàn)Γ（Λ'j)∩Γ（Λ'k)=?，1≤j≠k≤ω.此外，Γ（Λ'1)∪Γ（Λ'2)∪…∪Γ（Λ'ω)=Γ是S（G)的全體2i個(gè)頂點(diǎn)的一級(jí)半子圖集合.由引理2.1，

參考文獻(xiàn)：

〔1〕A．K．Kel’mans，V．M．Chelnokov．A certain polynomial of a graph and graphs with an extremal number of trees[J]．J．Combin．Theory，Ser．B，1974，16：197－214．Erratum [J]．J．Combin．Theory，Ser．B，1978，24：375．

〔2〕N．L．Biggs．Algebraic Graph Theory [M]．Cambridge：Cambridge University Press，1993．

〔3〕D．Cvetkovi？，P．Rowlinson，S．K．Simi？．Signless Laplacians of finite graphs [J]．Linear Algebra and its Applications，2007，423：155－171．

〔4〕S．Akbari，E．Ghorbani，J．H．Koolen，M．R．Oboudi．A relation between the Laplacians and signless Laplacians eigenvalues of graph[J]．Alg．Combin．，2010，32：459－464．

〔5〕B．Zhou，I．Gutman．A connection between ordinary and Laplacians spectra of bipartite graphs [J]．Linear and Multilinear Algebra，2008，56：305－310．

〔6〕W．G．Yan，Y．-N．Yeh．Connections between Wiener index and matchings[J]．Math．Chem．，2006，39：389－399．

中圖分類號(hào)：O157.5

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1673-260X（2015）09-0007-03