單圈圖的最大拉普拉斯分離度

黃冬明，方　怡，余桂東

(安慶師范大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，安徽 安慶 246133)

?

單圈圖的最大拉普拉斯分離度

黃冬明，方怡，余桂東

(安慶師范大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，安徽 安慶 246133)

單圈圖；圖的拉普拉斯分離度；圖的拉普拉斯矩陣

設(shè)G=(V(G),E(G))是一個n階簡單連通圖，其頂點(diǎn)集V(G)={v1,v2,…,vn}，邊集E(G)={e1,e2,…,em}。若m=n，則稱G是單圈圖。通常情況下，用Kn、K1,n-1、Cn、Pn分別表示n個頂點(diǎn)的完全圖、星圖、圈和路。

下面給出相關(guān)引理。

假設(shè)G1和G2是兩個頂點(diǎn)集不相交的圖，其中v1∈V(G1),v2∈V(G2)，圖G1和G2的粘圖記為G1·G2，其中V(G1·G2)=V(G1)∪V(G2)∪({v*}-{v1,v2})，G1·G2中的兩個頂點(diǎn)相鄰，當(dāng)且僅當(dāng)它們在G1或G2中相鄰，或者，如果一個頂點(diǎn)是v*，則另一個頂點(diǎn)和v1或v2相鄰。

用Lv(G)表示由L(G)刪掉頂點(diǎn)v相應(yīng)的行和列后所得的主子矩陣。為了方便，記

Φ(G;x)=det[xI-L(G)],

Φ[Lv(G);x]=det[xI-Lv(G)]。

引理4[6]設(shè)G1·G2如上述所定義，則有Φ(G1·G2;x)=Φ(G1;x)Φ[Lv2(G2);x]+Φ(G2;x)Φ[Lv1(G1);x]-xΦ[Lv1(G1);x]Φ[Lv2(G2);x]。

圖1為n階最大度為n-1的單圈圖Un。

圖1　Un

通過簡單計(jì)算，得到下面的結(jié)論：

引理5Φ(K1,n;x)=x(x-n-1)(x-1)n-1，Φ[Lv2(K1,n);x]=(x-1)n，其中v2是K1,n的中心；Φ(C3;x)=x(x-3)2，Φ[Lv1(C3);x]=(x-1)(x-3)，其中v1是C3的某個頂點(diǎn)。

引理6設(shè)Un如圖1所示，則當(dāng)n≥5時，SL(Un)=n-3。

證明將Un看作由C3的某個頂點(diǎn)v1和K1,n-3的中心點(diǎn)v2所粘合得到的圖，由引理4與引理5可得

用g(G)表示圖G中最短圈的長度，Δ(G)為圖G的最大度，An表示n階單圈圖的集合。圖2中F1、F2、F3為3個g(G)=3的5階單圈圖。

圖2　F1、F2和F3

下面是本文的主要結(jié)論。

定理1設(shè)G是An中的任意一個圖，則當(dāng)n≥8時，有SL(G)≤SL(Un)，當(dāng)且僅當(dāng)G=Un等號成立。

證明若G∈An，且Δ(G)=n-1，則G=Un，則結(jié)論成立。

下面證明當(dāng)G∈An，且Δ(G)≤n-2時，有

SL(G)

(1)

(2)

(3)

由(1)式和(3)式，可得

下面將分2種情形來討論：當(dāng)g(G)=3時，F(xiàn)1∪(n-5)K1,F2∪(n-5)K1或F3∪(n-5)K1中的某個圖是G的生成子圖。通過計(jì)算可得

(4)

這樣由引理2可得

[1]YouZF,LiuBL.ThesignlessLaplacianseparatorofgraphs[J].ElectronicJournalofLinearAlgebra, 2011, 22: 151-160.

[2]LiJX,CheeW,ChanWH.SomeresultsontheLaplacianeigenvaluesofunicyclicgraphs[J].LinearAlgebraAppl, 2009, 430(8/9): 2080-2093.

[3] 簡相國，袁西英，張曼. 單圈圖和雙圈圖的最大無符號拉普拉斯分離度[J]. 運(yùn)籌學(xué)學(xué)報, 2015, 19(2): 9-104.

[4]CvetkovicDM,DoobM,SacksH.SpectraofGraphs:TheoryandApplications[M].NewYork:AcademicPress, 1979.

[5]MerrisR.AnoteonLaplaciangrapheigenvalues[J].LinearAlgebraAppl, 1998, 285: 33-35.

[6]YuanXY.ANoteonthelaplacianspectralradiiofbicyclicgraphs[J].Advancesinmathematics, 2010, 6: 703-708.

The Maximum Laplacian Separator of Unicyclic Graphs

HUANG Dong-ming, FANG Yi, Yu Gui-dong

(School of Mathematics and Computation Sciences, Anqing Normal University, Anqing, Anhui 246133, China)

unicyclic graph; the Laplacian separator of graph; Laplacian matrix

2016-03-01

安徽省高校自然科學(xué)基金(KJ2015ZD27，AQKJ2015B010)。

黃冬明，男，安徽含山人，安慶師范大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院碩士研究生，研究方向?yàn)閳D論。E-mail: 719004685@qq.com

http://www.cnki.net/kcms/detail/34.1150.N.20160817.1131.006.html

O157.5

A

1007-4260(2016)03-0018-03

10.13757/j.cnki.cn34-1150/n.2016.03.006