管婷婷

(安慶師范學(xué)院 音樂學(xué)院，安徽 安慶 246133)

?

給定控制數(shù)的樹的代數(shù)連通度

管婷婷

(安慶師范學(xué)院 音樂學(xué)院，安徽 安慶 246133)

摘要：一個(gè)圖G(V,E)的控制數(shù)γ(G)是V的這樣一個(gè)子集S的最小基數(shù)，使得G中每一個(gè)頂點(diǎn)或者在S中或者和S中的一些頂點(diǎn)鄰接.討論給定控制數(shù)的樹的代數(shù)連通度,得出樹T*=K1，y-1°K1具有最大的代數(shù)連通度；同時(shí)利用移接變形刻畫出給定控制數(shù)2的樹中具有最小代數(shù)連通度的極圖,得出樹T=T3(s3,t3)具有最小的代數(shù)連通度.

關(guān)鍵詞：控制數(shù)；樹；代數(shù)連通度

目前已經(jīng)有許多文章研究樹的拉普拉斯譜半徑與圖的一些不變量之間的關(guān)系.例如:Hong和Zhang[1]研究了給定懸掛點(diǎn)數(shù)的樹的拉普拉斯譜半徑并確定了其中具有最大譜半徑的極圖;Guo[2]研究了樹的拉普拉斯譜半徑和直徑的關(guān)系;馮立華[3]研究了給定控制數(shù)的樹的拉普拉斯譜半徑并且確定了該類樹中具有最小譜半徑的極圖;Guo[4]研究了給定邊獨(dú)立數(shù)的樹的拉普拉斯譜半徑的上界,并刻畫出極圖.本文將討論給定控制數(shù)的樹的代數(shù)連通度,刻畫出具有最小代數(shù)連通度的極圖.

1引理

引理2[6]對(duì)于樹T，有α(T)1,等號(hào)成立當(dāng)且僅當(dāng)T?K1,n-1.

引理4[8-9]令e=uv是連通圖G的一條割邊且G-uv=G1∪G2,|V(Gi)|≥2,(i=1,2),u∈V(G1),v∈V(G2).在G中分離邊uv得到圖G′,則α(G)α(G′).并且當(dāng)X(ue)≠0或X(ve)≠0時(shí)不等號(hào)嚴(yán)格成立,其中X是G′的對(duì)應(yīng)于α(G′)的Fiedler向量.

2主要結(jié)論

定理1具有n個(gè)頂點(diǎn),控制數(shù)γ=1的樹T,代數(shù)連通度α(T)=1.

證明若γ=1,此時(shí)只有一個(gè)圖,就是星圖K1,n-1.因?yàn)樾菆D的拉普拉斯特征多項(xiàng)式為Φ(L(K1,n-1))=μ(μ-n)(μ-1)n-2,所以α(T)=μn-1(K1,n-1)=1.

2.2控制數(shù)為γ=2的樹.

對(duì)于任意的n階樹,要使它滿足控制數(shù)γ=2,可以構(gòu)造出下面三類樹:(I)取一條具有4個(gè)頂點(diǎn)的路,在它的第2和第3個(gè)頂點(diǎn)處分別粘貼s1和t1條懸掛邊,得到的圖記為T1(s1,t1),γ=2s1+t1+4=n;(Ⅱ)取一條具有5個(gè)頂點(diǎn)的路,在它的第2和第4個(gè)頂點(diǎn)處分別粘貼s2和t2條懸掛邊,得到的圖記為T2(s2,t2),s2+t2+5=n;(Ⅲ)取一條具有6個(gè)頂點(diǎn)的路,在它的第2和第5個(gè)頂點(diǎn)處分別粘貼s3和t3條懸掛邊,得到的圖記為T3(s3,t3),s3+t3+6=n.如圖1所示.

圖1　控制數(shù)γ=2的三類樹

定理4所有具有n個(gè)頂點(diǎn),控制數(shù)γ=2的樹中,樹T=T3(s3,t3)具有最小的代數(shù)連通度.

證明因?yàn)閐T2(v1)≥2,dT2(vw)=2,v1w是樹T2(s2,t2)的割邊,所以對(duì)T2(s2,t2)分離邊v1w得到T1(s2+1,t2),由引理4可知,α(T2(s2,t2))α(T1(s2+1,t2)).而T1(s2+1,t2)?T1(s1,t1),因此α(T2(s2,t2))α(T1(s1,t1)).

因?yàn)閐T3(v1)≥2,dT3(vu)=2,v1u是樹T3(s3,t3)的割邊,所以對(duì)T3(s3,t3)分離邊v1u得到T2(s3+1,t3),由引理4可知,α(T3(s3,t3))α(T2(s3+1,t3)).而T2(s3+1,t3)?T2(s2,t2),因此α(T3(s3,t3))α(T2(s2,t2)).

所以,α(T3(s3,t3))α(T2(s2,t2))α(T1(s1,t1)).

[參考文獻(xiàn)]

[1]HONG Y,ZHANG X D.Sharp upper and lower bounds for largest eigenvalue of the Laplacian matrix of trees[J].Discrete Math.,2005(296):187-197.

[2]GUO J M.On the Laplacian spectral radius of trees with fixed diameter[J].Linear Algebra Appl.,2006(419)：618-619.

[3]FENG L H,YU G H,LI Q.Minimizing the Laplacian eigenvalues for trees with given domination number[J].Linear Algebra Appl.,2006(419)：648-655.

[4]GUO J M.On the Laplacian spectral radius of a tree[J].Linear Algebra Appl.,2003(368)：379-387.

[5]FINK J F,JACOBSON M S,KINCH L F,et al. On graphs having domination number half their order[J].Period.Math.Hungar,1985(16):287-293.

[6]KIRKLAND S.A bound on the algebraic connectivity of a graph in terms of the number of cutpoints[J].Linear and Multilinear Algebra,2000(47)：93-103.

[7]FIEDLER M,PRAHA.Algebraic connectivity of graph[J].Czechoslovak Math.,1973(23):298-305.

[8]GUO J M.On the second largest Laplacian eigenvalue of trees[J].Linear Algebra Appl,2005(404):251-261.

[9]GUTMAN I.The star is the tree with greatest greatest Laplacian eigenvalue[J].Kragujevac J Math.,2002(24):61.

[責(zé)任編輯王新奇]

AlgebraicConnectivityofTreeswithGivenDominationNumber

GUAN Ting-ting

( School of Music, Anqing Normal University, Anqing 246133, China )

Abstract：The domination number γ(G) of a graph G(V,E) is the minimum cardinality of a subset of V, and it makes every vertex is either in the set S or adjacent to some vertices in the set S. In this paper, the algebraic connectivity of the tree T*=K1，°K1with given domination number 1, was discussed, and the conclusion of the tree has the largest algebraic connectivity was got. At the same time, the polar graph with the smallest algebraic connectivity among trees in a given domination number 2 was depicted by using of shift in deformation, and the conclusion of the tree T=T3(s3,t3) has the smallest algebraic connectivity was got.

Key words：domination number; trees; algebraic connectivity

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

文獻(xiàn)標(biāo)志碼：A

作者簡介：管婷婷(1984—)，女，安徽安慶人，安慶師范學(xué)院音樂學(xué)院助教，碩士，主要從事圖論與網(wǎng)絡(luò)優(yōu)化研究.

收稿日期：2015-10-25

文章編號(hào)：1008-5564(2016)01-0005-03