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

管婷婷

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

?

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

管婷婷

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

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

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

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

1引理

引理2[6]對于樹T，有α(T)1,等號成立當且僅當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′).并且當X(ue)≠0或X(ve)≠0時不等號嚴格成立,其中X是G′的對應于α(G′)的Fiedler向量.

2主要結論

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

證明若γ=1,此時只有一個圖,就是星圖K1,n-1.因為星圖的拉普拉斯特征多項式為Φ(L(K1,n-1))=μ(μ-n)(μ-1)n-2,所以α(T)=μn-1(K1,n-1)=1.

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

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

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

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

證明因為dT2(v1)≥2,dT2(vw)=2,v1w是樹T2(s2,t2)的割邊,所以對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)).

因為dT3(v1)≥2,dT3(vu)=2,v1u是樹T3(s3,t3)的割邊,所以對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)).

[參考文獻]

[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.

[責任編輯王新奇]

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

中圖分類號：O157.5

文獻標志碼：A

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

收稿日期：2015-10-25

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