譚尚旺,姜靜靜

(中國(guó)石油大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,山東東營(yíng) 257061)

關(guān)于樹的第二個(gè)最大特征值

譚尚旺,姜靜靜

(中國(guó)石油大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,山東東營(yíng) 257061)

樹;匹配;譜半徑;第二個(gè)最大特征值

1 問題的提出

設(shè) G是具有 n個(gè)頂點(diǎn)的無向簡(jiǎn)單圖。記 G的鄰接矩陣為A(G),稱 A(G)的特征多項(xiàng)式 det(λE -A(G))為 G的特征多項(xiàng)式,記為 φ(G,λ)。既然A(G)是一個(gè)實(shí)對(duì)稱矩陣,于是它的特征值都是實(shí)數(shù),不妨設(shè)它們按照不降的次序排列為

稱λk(G)是 G的第 k個(gè)最大特征值,稱λ1(G)為 G的譜半徑。

G的兩個(gè)不同邊在 G中稱為獨(dú)立的,如果它們?cè)贕中不鄰接。G的一個(gè)兩兩獨(dú)立的邊集合稱為G的一個(gè)匹配,邊數(shù)最多的匹配稱為 G的最大匹配并且一個(gè)最大匹配的邊數(shù)稱為 G的匹配數(shù)。令M是 G的一個(gè)最大匹配,如果 G的頂點(diǎn) v與M中的一個(gè)邊關(guān)聯(lián),則稱 v被M飽和;如果 G的每個(gè)頂點(diǎn)都被M飽和,則稱M是 G的一個(gè)完美匹配。

二部圖的特征值在量子化學(xué)理論中有其物理意義[1]。Cvetkovic′D M曾經(jīng)指出了圖譜理論的幾個(gè)進(jìn)一步研究的方向,其中之一就是對(duì)圖進(jìn)行分類和定序 (classifying and ordering graphs)[2]。既然樹是特殊的二部圖并且它在圖論中起著重要的作用,于是研究樹的圖論性質(zhì)與它的特征值之間的關(guān)系是有意義和必要的。

令 T(n,i)表示頂點(diǎn)數(shù)為 n且匹配數(shù)為 i的所有樹的集合。長(zhǎng)期以來,許多學(xué)者一直利用樹的譜半徑對(duì)樹定序[3-7]。但是,如何利用樹的其他特征值對(duì)樹進(jìn)行定序的研究較少。特別是利用樹的第二個(gè)最大特征值對(duì) T(n,i)中的樹進(jìn)行定序取得的結(jié)論更少,目前只有當(dāng) n=2i,2i+1,2i+2時(shí)有幾個(gè)結(jié)論被得到[8-11]。

文獻(xiàn)[11]中證明了下述結(jié)論:對(duì) T∈T(4n-1, 2n-1),都有

并且該上界是可達(dá)的。文獻(xiàn)[11]中猜想:在 T(4n -1,2n-1)中,只有 4個(gè)樹的第二個(gè)最大特征值能夠達(dá)到該上界。本文中證明該猜想的正確性,并且對(duì) T∈T(4n-1,2n-1),給出λ2(T)的 3個(gè)新的上界并確定達(dá)到上界的所有樹。貫穿全文,令 o(G)表示圖 G的頂點(diǎn)數(shù),i(G)表示 G的匹配數(shù),G?H表示圖G和H同構(gòu)。特別記

引理 1[1]令 vu是樹 T的一個(gè)邊,則 φ(T,λ) =φ(T-vu,λ)-φ(T-v-u,λ)。

文獻(xiàn)[5-7]中研究了 T(n,i)中樹的譜半徑,綜合這 3個(gè)文獻(xiàn)的結(jié)論有下面的引理。

圖 1 譜半徑最大的前六個(gè)樹Fig.1 The first six trees with the largest spectral radius

引理 4[1]令 G是頂點(diǎn)數(shù)為 n的無向圖,V′是G的一個(gè) k點(diǎn)子集,G-V′表示從G中刪去V′中的所有頂點(diǎn)以及與 V′中的點(diǎn)關(guān)聯(lián)的所有邊后得到的 G的子圖,則

2 主要結(jié)論及證明

由于

由引理 2知,λ1(T32n,n)是方程φ(λ)=0的最大正根,其中

由于

由引理 2知,λ1()是方程ω(λ)=0的

最大正根,其中

由于

令Wj(j=1,2,…,20)是圖 2中所示的樹,記ξj=λ(λ2-1)2n-j, θ(s,t)=λ4-sλ2+t.

圖 2 T(4n-1,2n-1)中的 20個(gè)樹Fig.2 Twenty trees ofT(4n-1,2n-1)

由引理 1,容易得到λ2θ(2,1)]-(λ2-1)θ(n,1)θ(n,2)}.

引理 6 如果 n≥8,則

(1)λ2(Wj)=δn+1,8,j=1,2,3,4。

(2)δn+1,11+εn<λ2(W7)<λ2(W6)<λ2(W5)< δn+1,8,其中λ2(W5),λ2(W6)和λ2(W7)依次是下面方程的第二大正根:

(3)λ2(Wj)<δn+1,11+εn,j=8,9,…,20.

證明 (1)對(duì) j=1,2,3,4,容易發(fā)現(xiàn)

并且由引理 4知,

因此,λ2(Wj)=δn+1,8。

于是 f(λ)的 4個(gè)正根分別位于區(qū)間 (0,βn+1,4), (βn+1,4,μ), (μ,δn+1,10), (δn+1,10,+∞)內(nèi),即

因此,對(duì) j=5,6,有

由 φ(W5,λ)和 φ(W6,λ)得

于是對(duì)δn+1,10<λ<δn+1,8,都有 φ(W5,λ)>φ(W6, λ)。因此,由上面的討論得

由式 (1)和式 (2)知,δn+1,11+εn<λ2(W7)<λ2(W6) <λ2(W5)<δn+1,8。

由上面的討論,對(duì) j=8,9,…,20,都有λ2(Wj)< δn+1,11+εn。

引理 7 令 T是一個(gè)樹,o(T)≤2n-2并且 T至多有兩個(gè)頂點(diǎn)不被它的某個(gè)最大匹配M飽和。如果 n≥6,則λ1(T)<δn+1,11+εn。

證明 如果 o(T)是奇數(shù),記 o(T)=2s-1,則 s≤n-1且 i(T)=s-1。由引理 2得

如果 o(T)是偶數(shù),記 o(T)=2s,則 s≤n-1且 i(T) =s,s-1。由引理 2得

定理 1不僅證明了文獻(xiàn) [11]中提出的猜想是正確的,而且也給出了λ2(T)的 3個(gè)新的上界。

定理 1 令 n≥9,Jk={Wj:j=1,2,…,k}并且T∈T(4n-1,2n-1)。

(1)λ2(T)≤δn+1,8,并且等式成立,當(dāng)且僅當(dāng) T∈J4。

(4)如果 T?J6,則λ2(T)≤λ2(W7),并且等式成立,當(dāng)且僅當(dāng) T?W7。

證明 假設(shè) T?J20,由引理 6,只需要證明下式:

在引理3中取 k=2n-1,則存在一個(gè)頂點(diǎn) v∈V(T),使得 T-v的每個(gè)分支,記為 Tj(j=1,2,…,l),都有 o(Tj)≤2n-1。由引理 4得

如果 Tj有完美匹配,記 o(Tj)=2sj,則 i(Tj)=sj≤n -1。由引理 2得

令M是 T-v的一個(gè)最大匹配,則 T-v至多有兩個(gè)頂點(diǎn)不被M飽和。區(qū)分下面 3種情形。

情形 1 設(shè) T-v的每個(gè)頂點(diǎn)都被M飽和。

對(duì) j=1,2,…,l,因?yàn)槊總€(gè) Tj有完美匹配,所以式(5)都成立。因此,由式 (4)知,式(3)成立。

情形 2 設(shè) T-v有兩個(gè)頂點(diǎn)不被M飽和并且它們?cè)?T-v的同一個(gè)分支中。

不失一般性,假設(shè) T1有兩個(gè)頂點(diǎn)不被M飽和,而 T-v的其他分支 Tj(j=2,3,…,l)都有完美匹配。令 o(T1)=2s1,則 s1≤n-1且 i(T1)=s1-1。由引理2得

因此,結(jié)合式(5)和式(4)知,式(3)成立。

情形 3 設(shè) T-v有兩個(gè)頂點(diǎn)不被M飽和并且它們?cè)?T-v的不同分支中。

不失一般性,假設(shè) T1和 T2都各有一個(gè)頂點(diǎn)不被M飽和,而 T-v的其他分支 Tj(j=3,4,…,l)都有完美匹配。對(duì) j=1,2,令 o(Tj)=2sj-1,則 sj≤n且 i(Tj)=sj-1。

對(duì) j=1,2,如果 sj≤n-1,則由引理 2得

對(duì) j=1,2,如果 sj=n且 Tj,則由引理2和引理5得

因此,當(dāng) T1并且 T2時(shí),由式 (5)和式 (4)知,式 (3)成立。不妨設(shè) T1?。令u是 v在 T1中的唯一鄰接頂點(diǎn),則存在 T-u的一個(gè)分支,比如說,包含并且 o()=2n,而 T -u的其他分支,比如說(j=2,3,…,r),都滿足o()≤2n-2。令是 T-u的一個(gè)最大匹配,則對(duì) j=1,2,…,r,至多有兩個(gè)頂點(diǎn)不被 ~M飽和。由引理4得

由引理 7,對(duì) j=2,3,…,r,都有

如果則 T∈J16,這與 TJ20矛盾。因此于是由引理 2和引理 5得λ1()≤ λ1()<δn+1,11+εn。因此,由式 (6)和式 (7)知,式(3)成立。

根據(jù)上面 3種情形,完成了式(3)的證明。

注釋:當(dāng) n=8時(shí),用 2.945 19代替引理 5～7和定理 1中的δn+1,11+εn,相應(yīng)的結(jié)論也都成立。因此,定理 1的結(jié)論對(duì) n=8也成立。

[3] HOFMEISTER M.On the two largest eigenvalues[J]. LinearAlgebra Appl,1997,260:43-59.

[4] CHANGA,HUANGQ X.Ordering trees by their largest eigenvalues[J].Linear Algebra Appl,2003,370:175 -184.

[5] HOU Y P,L I J S.Bounds on the largest eigenvalues of treeswith a given size of matching[J].Linear Algebra Appl,2001,342:203-217.

[6] 譚尚旺,郭紀(jì)明.樹的最大特征值 [J].石油大學(xué)學(xué)報(bào):自然科學(xué)版,2002,26(6):113-117.TAN Shang-wang,GUO Ji-ming.The largest eigenvalue on trees[J].Journal of the University of Petrolum (Edition ofNatural Science),China,2002,26(6):113 -117.

[7] 譚尚旺.給定邊獨(dú)立數(shù)的樹的譜半徑的新上界 [J].廣西工學(xué)院學(xué)報(bào),2008,19(1):13-17.

TAN Shang-wang.On the new upper bounds of spectral radius of trees given edge independence number[J]. Journal of Guangxi Unversity of Technology,2008,19 (1):13-17.

[8] GUO J M,TAN SW.A conjecture on the second largest eigenvalue of a tree with perfect matchings[J].Linear Algebra Appl,2002,347:9-15.

[9] GUO JM,TAN SW.A note on the second largest eigenvalue of a tree with perfectmatching[J].LinearAlgebra Appl,2004,380:125-134.

[10] 譚尚旺,郭紀(jì)明.樹的第二個(gè)最大特征值[J].數(shù)學(xué)研究與評(píng)論,2004,24(3):541-548.

TAN Shang-wang,GUO Ji-ming.The second largest eigenvalues of trees[J].Journal of Mathematical Research and Exposition,2004,24(3):541-548.

[11] TAN Shang-wang,GUO Ji-ming.The second largest eigenvalue of trees[J].Australasian Journal of Combinatorics,2006,34:313-320.

[12] SHAO J Y.Bounds on the kth eigenvalues of trees and forests[J].LinearAlgebra Appl,1991,149:19-34.

(編輯 修榮榮)

On the second largest eigenvalue of trees

TAN Shang-wang,J IANG Jing-jing
(College of M athem atics and Computational Science in China University of Petroleum, Dongying257061,China)

trees;matching;spectral radius;the second largest eigenvalue

O 157.5

A

10.3969/j.issn.1673-5005.2010.02.035

1673-5005(2010)02-0169-06

2009-06-20

國(guó)家自然科學(xué)基金項(xiàng)目(10871204)

譚尚旺(1965-),男(漢族),山東泰安人,教授,碩士,研究方向?yàn)閳D論。