邱瑋

幾類圖的無符號Laplace矩陣的行列式

邱瑋

（福州外語外貿(mào)學(xué)院，福建福州 350202）

無符號Laplace矩陣；行列式；樹；連通單圈圖；連通雙圈圖

我們知道n個頂點的圖G的Laplace特征值按非增排列為：λ1≥…≥λn=0，于是G的Laplace矩陣L(G)=D(G)-A(G)的行列式等于0，這里A(G)和D (G)分別是G的鄰接矩陣和度對角矩陣，這是一個一般規(guī)律.那么n個頂點的圖G的無符號Laplace矩陣Q(G)=D(G)+A(G)的行列式是否有確定的值？

1 圖論的基本概念

定義1.1一個圖是由非空點集V=V(G)和V中元素的無序?qū)Φ囊粋€集合E=E(G)所構(gòu)成的二元組,記為G=(V(G),E(G)),簡記為G=(V,E).邊ek可以用它的兩個端點vi和vj表示，記為(vi,vj)或vivj.V中的元素稱為頂點,E中的元素稱為邊.我們用n(G)=|V|表示G的頂點數(shù),簡記為n.用m(G)=|E|表示G的邊數(shù),簡記為m.對u,v∈V(G)，若e=uv∈E(G)，則稱u和v相鄰，同時也稱u及v與e相關(guān)聯(lián).若e1,e2∈E (G)有一個公共頂點，則稱e1和e2相鄰.

定義1.2圖G=(V,E)中，與頂點v相關(guān)聯(lián)的邊數(shù)，稱為頂點v的度，記為dG(v)，簡記為d(v).

定義1.3圖G=(V,E)中，如果兩條邊有相同的兩端點，則稱它們?yōu)橹剡吇蚱叫羞叄绻粭l邊的兩端點相同，就稱它為環(huán).稱不包含環(huán)和重邊的圖為簡單圖.本文主要討論簡單圖.

定義1.4對于圖G和H，如果V(H)?V(G)，E (H)?E(G)，則稱H是G的子圖,如果H是G的子圖,并且V(H)=V(G),則稱H是G的生成子圖.

定義1.5如果圖G的一個頂點和邊的交替序列v0e1v1e2v2…vm-1emvm使得對1≤i≤m，邊ei的兩個端點是vi-1和vi，則稱該序列為G的一條路徑.又如果邊e1,e2,…,em互不相同，則稱該路徑為G的一條跡（或叫鏈）.頂點互不相同的跡稱為G的一條路.路中邊的條數(shù)稱為該路的長度,圖G中u,v兩點的距離是指以u與v為起止點的u-v路的最短路長，記為dG(u,v).

定義1.6對于圖G的兩個頂點u和v，如果G中存在一條路，記為(u,v)路，則稱u和v是連通的.如果一個圖的每一對頂點都至少有一條路連結(jié)，則稱該圖為連通圖.

定義1.7在圖G中頂點的連通關(guān)系下，可將V(G)劃分成有限個等價類，每個等價類構(gòu)成G的子圖，稱為G的一個連通分支.

定義1.8圈C是指頂點集為V(C)={v1,v2,…, vn}，邊集為E(C)={v1v2,…,vn-1vn,vnv1}的圖，記為圈Cn，n=|E(C)|為圈的長度.按n是奇數(shù)還是偶數(shù)，稱Cn是奇圈或偶圈.

定義1.9沒有圈的連通圖稱為樹，記為T，每個連通分支皆為樹的圖稱為森林.如果T為樹，則n (T)=m(T)+1，這里n(T)與m(T)分別為T的頂點數(shù)與邊數(shù).

定義1.10由樹添加一條邊所得到的連通圖稱為單圈圖,記為U.顯然，n(U)=m(U).

定義1.11由樹添加兩條邊所得到的連通圖稱為雙圈圖,記為W.顯然，n(W)=m(W)-1.

定義1.12設(shè)圖G的頂點集為V(G)={v1,v2,…, vn}，用aij表示G中vi和vj之間的邊數(shù).稱A(G)=(aij)n×n為G的鄰接矩陣.若點vi的度為d(vi)(i=1,2,3…n)，則G的度對角矩陣定義為diag(d(v1),d(v2),…d(vn) )，簡記為D(G)，無符號Laplace矩陣Q(G)定義為：Q (G)=D(G)+A(G).

2 已有的結(jié)果

定義2.1[4,6]圖G的一個生成子圖稱為G的TU-子圖H，如果它的每個分支是樹或者是非偶單圈圖.

利用圖G的TU-子圖，Cvetkovic等[6]給出了圖的無符號Laplace特征多項式的系數(shù)的一個組合解釋如下：

3 本文的結(jié)果

首先我們給出n個頂點的樹的無符號Laplace矩陣的行列式的值.

定理3.1設(shè)T是n個頂點的樹，T的無符號Laplace矩陣為Q(T)=D(T)+A(T)，則：

證明T的無符號Laplace特征多項式為：

下面我們考慮單圈圖的無符號Laplace矩陣的行列式的計算問題.

定理3.2設(shè)G是n個頂點的連通單圈圖，其中圈的長度為g，G的無符號Laplace矩陣為Q(G) =D(G)+A(G)，則：

證明G的無符號Laplace特征多項式為：

下面我們再考慮雙圈圖的無符號Laplace矩陣的行列式的計算問題，我們得到如下三個定理.

定理3.3設(shè)G是n個頂點的連通雙圈圖，其中兩個圈為C1與C2，它們的長度分別為g1與g2，且C1與C2相交于一個頂點，G的無符號Laplace矩陣為Q(G)=D(G)+A(G)，則：

定理3.4設(shè)G是n個頂點的連通雙圈圖，其中兩個圈為C1與C2，它們的長度分別為g1與g2，且C1與C2不相交，C1與C2之間距離為g3，G的無符號Laplace矩陣為Q(G)=D(G)+A(G)則：

定理3.5設(shè)G是n個頂點的連通雙圈圖，其中兩個圈為C1與C2，它們的長度分別為g1與g2，若C1與C2有公共邊，且公共邊的數(shù)目為g4，G的無符號Laplace矩陣為Q(G)=D(G)+A(G)則：

3.1 C1與C2相交于一個頂點，如圖1.

圖1 雙圈圖G，其中兩個圈交于一個頂點

（1）當g1,g2都為偶數(shù)時，去掉任何一條邊都不能形成n條邊的TU-子圖.根據(jù)定理2.2，det(Q(G)) =bn=0.

（2）當g1為奇數(shù)，g2為偶數(shù)時，去掉C2以外的任何一條邊都不能形成n條邊的TU-子圖；去掉C2上的任何一條邊都形成G的一個n條邊的TU-子圖H，此時Φ(H)=4.根據(jù)定理2.2，det(Q(G))=bn=

（3）當g1為偶數(shù)，g2為奇數(shù)時，同（2）的情況一樣可得：det(Q(G))=4g1.

（4）當g1,g2都為奇數(shù)時，去掉C1,C2以外的任何一條邊都不能形成n條邊的TU-子圖；去掉C1,C2上的任何一條邊都會形成G的一個n條邊的TU-子圖H，此時Φ(H)=4.又因為C1,C2的長度分別為g1,g2，根據(jù)定理2.2

3.2 C1,C2不相交，且C1,C2之間的距離為g3，如圖2所示.

圖2 雙圈圖G，其中兩個圈沒有交點

（1）當g1,g2都為偶數(shù)時，去掉任何一條邊都不能形成n條邊的TU-子圖.根據(jù)定理2.2，det(Q(G)) =bn=0.

（2）當g1為奇數(shù)，g2為偶數(shù)時，去掉C2以外的任何一條邊都不能形成n條邊的TU-子圖；而去掉C2上的任何一條邊都形成G的一個n條邊的TU-子圖H，此時Φ(H)=4.根據(jù)定理2.2，det(Q(G))

（3）當g1為偶數(shù)，g2為奇數(shù)時，同（2）情況一樣可得：det(Q(G))=(-1)n4g1.

（4）當g1,g2都為奇數(shù)時，去掉C1,C2和C1,C2之間相連的邊以外的任何一條邊都不能形成n條邊的TU-子圖；去掉C1,C2上的任何一條邊都會形成G的一個n條邊的TU-子圖H，此時Φ(H)=4；去掉C1,C2之間相連的任何一條邊也都會形成G的一個n條邊的TU-子圖H，此時Φ(H)=4×4=16.根據(jù)定理2.2

3.3 C1,C2有公共邊，且公共邊的數(shù)目為g4，如圖3.

（1）當g1,g2都為偶數(shù)時，去掉任何一條邊都不能形成n條邊的TU-子圖.根據(jù)定理2.2，det(Q(G)) =bn=0.

圖3 雙圈圖G，其中任意兩圈都相交

（2）當g1為奇數(shù)，g2為偶數(shù)時，去掉C2以外的任何一條邊都不能形成n條邊的TU-子圖；去掉C2上除去公共邊的任何一條邊都會形成G的一個n條邊的TU-子圖；去掉C1,C2的任何一條公共邊都會得到一個圈長為g1+g2-2g4的單圈圖，由于g1為奇數(shù)，g2為偶數(shù)，g1+g2-2g4≡1(mod2)，這個單圈圖也是TU-子圖，所以去掉C2上的任何一條邊都形成G的一個n條邊的TU-子圖H，此時Φ(H)=4.根據(jù)定理2.2

（3）當g1為偶數(shù)，g2為奇數(shù)時，同（2）的情況一樣可得：det(Q(G))=4g1.

（4）當g1,g2都為奇數(shù)時，去掉C1,C1以外的任何一條邊都不能形成n條邊的TU-子圖；去掉C1,C2上除公共邊外的任何一條邊，都會形成G的一個n條邊的TU-子圖H，此時Φ(H)=4；去掉C1,C2的任何一條公共邊都會得到一個圈長為g1+g2-2g4的單圈圖，由于g1,g2都為奇數(shù)，g1+g2-2g4≡0(mod2)，這個單圈圖不是TU-子圖，所以去掉C1,C2的任何一條公共邊都不會形成n條邊的TU.根據(jù)定理2.2，

綜上所述，定理3.3、定理3.4與定理3.5得證.

本文主要研究n個頂點的樹、連通單圈圖與連通雙圈圖的無符號Laplace矩陣的行列式的計算問題，給出了計算這三類圖的無符號Laplace矩陣的行列式的一般方法，對研究圖的無符號Laplace矩陣的行列式有著重要的意義.

〔1〕王樹禾.圖論［M］.北京：科學(xué)出版社，2004.

〔2〕孫惠泉.圖論及其應(yīng)用［M］．北京：科學(xué)出版社，2004.

〔3〕劉纘武.應(yīng)用圖論［M］．湖南：國防科技大學(xué)出版社，2006.

〔4〕邱瑋.圖的Laplace特征多項式系數(shù)的若干結(jié)果［D］．集美大學(xué)，2012.

〔5〕林偉奇.樹的Laplace特征多項式的系數(shù)序［D］.集美大學(xué)，2011.

〔6〕Cvetkovic，Rowlinson，Simic.SignlessLaplacians of finite graphs［J］.Linear Algebra and Applications，2007（423）：155-171.

O151

A

1673-260X（2015）04-0004-03