圖的無符號Laplace特征多項式的系數

邱瑋（福州外語外貿學院　經濟學院，福建　福州　350202）

圖的無符號Laplace特征多項式的系數

邱瑋
（福州外語外貿學院經濟學院，福建福州350202）

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

關鍵詞：剖分圖；一級半子圖；Laplace特征多項式；無符號Laplace特征多項式

1　背景介紹

設G是b個頂點m條邊的連通簡單圖，A（G)，B（G)和D （G)分別是G的鄰接矩陣，關聯矩陣和度對角矩陣，Q（G)=D （G)-A（G)是G的Laplace矩陣，Q（G)=D（G)+A（G)是G的無符號Laplace矩陣.

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

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

用g（G;x)表示圖G的無符號Laplace特征多項式，即

給出圖的TU-子圖的定義：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個分支T1，T2，…，Ts，U1，U2，…，Ut，其中Ti（1≤i≤s)是ni個頂點的樹，Uj（1≤j≤t)是非偶單圈圖.

定理1.3[4]對任意n個頂點的連通圖G，ai（G)≤bi（G)，i=0，1，…，n，等式成立當且僅當G是偶圖.

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

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

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

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

圖G的剖分圖S（G)為在G的每條邊e上插入一個新頂點所得到的圖.關于偶圖G的Laplace特征多項式與它的剖分圖S（G)的特征多項式之間的關系，Zhou和Gutman得到了下面的結果：

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

2　定理1.2的證明

得S（G)的特征多項式為：

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

=xm-ng（G;x2)

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

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

我們發現

注意到S（G)沒有奇圈，于是

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

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

為了闡明結論，先引入下面記號.

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

下面給出的結論是定理1.2證明的重要基礎.

結論1 Λ'有i條邊.

結論2 Λ是S（Λ')的一級半子圖.特別地，Λ恰好含有S（Λ')中的i個v-型頂點和i個e-型頂點.

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

由結論1和結論2，對于j=1，2，…，t，Λ恰好包含S（Hj)中的|E（Hj)|個v-型頂點和|E（Hj)|個e-型頂點.又因為|E（Hj)| ≤|V（Hj)|，于是|E（Hj)|=|V（Hj)|，即Hj（1≤j≤t)是單圈圖.結論3成立.

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

結論4對于1≤j≤t，S（Hj)恰有三組V（S（Hj))個頂點的一級半子圖：M1（Cj)∪M（S（Hj)-Cj)，M2（Cj)∪M（S（Hj)-Cj)和Cj∪M （S（Hj)-Cj).

結論5設Λ1是S（Λ')的2i個頂點的一級半子圖.則Λ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))個頂點的一級半子圖.

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

由結論5和引理2.2，我們得到

結論7對任意Λk∈Γ（Λ')，Λk'=Λ'.

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

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

記

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

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

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

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

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

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

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

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

參考文獻：

〔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．

中圖分類號：O157.5

文獻標識碼：A

文章編號：1673-260X（2015）09-0007-03