幾類(lèi)圖的無(wú)符號(hào)Laplace矩陣的行列式

邱瑋

幾類(lèi)圖的無(wú)符號(hào)Laplace矩陣的行列式

邱瑋

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

無(wú)符號(hào)Laplace矩陣；行列式；樹(shù)；連通單圈圖；連通雙圈圖

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

1 圖論的基本概念

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

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

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

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

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

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

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

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

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

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

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

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

2 已有的結(jié)果

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

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

3 本文的結(jié)果

首先我們給出n個(gè)頂點(diǎn)的樹(shù)的無(wú)符號(hào)Laplace矩陣的行列式的值.

定理3.1設(shè)T是n個(gè)頂點(diǎn)的樹(shù)，T的無(wú)符號(hào)Laplace矩陣為Q(T)=D(T)+A(T)，則：

證明T的無(wú)符號(hào)Laplace特征多項(xiàng)式為：

下面我們考慮單圈圖的無(wú)符號(hào)Laplace矩陣的行列式的計(jì)算問(wèn)題.

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

證明G的無(wú)符號(hào)Laplace特征多項(xiàng)式為：

下面我們?cè)倏紤]雙圈圖的無(wú)符號(hào)Laplace矩陣的行列式的計(jì)算問(wèn)題，我們得到如下三個(gè)定理.

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

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

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

3.1 C1與C2相交于一個(gè)頂點(diǎn)，如圖1.

圖1 雙圈圖G，其中兩個(gè)圈交于一個(gè)頂點(diǎn)

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

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

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

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

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

圖2 雙圈圖G，其中兩個(gè)圈沒(méi)有交點(diǎn)

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

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

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

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

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

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

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

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

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

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

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

本文主要研究n個(gè)頂點(diǎn)的樹(shù)、連通單圈圖與連通雙圈圖的無(wú)符號(hào)Laplace矩陣的行列式的計(jì)算問(wèn)題，給出了計(jì)算這三類(lèi)圖的無(wú)符號(hào)Laplace矩陣的行列式的一般方法，對(duì)研究圖的無(wú)符號(hào)Laplace矩陣的行列式有著重要的意義.

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

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

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

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

〔5〕林偉奇.樹(shù)的Laplace特征多項(xiàng)式的系數(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