馬志輝

（石河子大學(xué) 理學(xué)院，新疆 石河子 832000）

論單圈圖的特征值上界

馬志輝

（石河子大學(xué) 理學(xué)院，新疆 石河子 832000）

以圖的譜來(lái)刻劃圖的結(jié)構(gòu)性質(zhì)是圖的譜理論中重要的研究問(wèn)題之一.一方面圖譜在量子化學(xué)、信息科學(xué)等學(xué)科中均有一系列的重要應(yīng)用.另一方面圖譜理論發(fā)展的同時(shí)也促進(jìn)和豐富了圖論和組合數(shù)學(xué)本身的研究,譜技巧已經(jīng)成為圖論和組合數(shù)學(xué)研究中一個(gè)重要的工具.本文證明了階連通單圈圖的第個(gè)特征值的上界

單圈圖；上界；特征值

1 引言

本文所研究的單圈圖是恰含一個(gè)圈的簡(jiǎn)單連通圖，單圈圖G的特征值就是它的鄰接矩陣A(G)的特征值，A(G)的特征，多項(xiàng)式記為P(G,λ)，如果G是一個(gè)n階單圈圖，則A (G)是一個(gè)n階對(duì)稱(0,1)矩陣，故A(G)的第n個(gè)特征值，也就是G的第n個(gè)特征值全為實(shí)數(shù)，我們可以按遞降次序?qū)⑺鼈兣帕袨椋?/p>

稱λk(G)為G的第k個(gè)特征值.

在沒(méi)有特別說(shuō)明的情況下，本文的G均代表n階連通的單圈圖.

洪淵證明了：

1：λ1(G)≤λ1(S2n)，當(dāng)n≥9的時(shí)候，有，其中Sn2是連接星圖Ktn-1的兩個(gè)一度點(diǎn)而得到的圖.

2.λ1(G)=λ1(S2n)GSn2其中表示同構(gòu).

邵嘉裕研究了n階樹(shù)T的特征值的上界，所得結(jié)果如下：

對(duì)全部n≠0(modk)時(shí)，上界是最好可能上界.

2.當(dāng)n=0(modk)，上界(1)中嚴(yán)格不等式成立，但是對(duì)于任意ε＞0，一般不成立.

3.當(dāng)n=0(modk)，存在n階樹(shù)T*，使得：

本文在上述研究基礎(chǔ)上，對(duì)n階連通單圈圖G的第個(gè)特征值的上界問(wèn)題證明了：

2 引理

引理1 柯西插入定理

設(shè)V是G的一個(gè)含個(gè)點(diǎn)的點(diǎn)子集，G-V表示G刪除V中點(diǎn)以及和V中點(diǎn)相關(guān)聯(lián)的所有邊后所得的子圖，則有：

證 設(shè)θ是G的非孤立點(diǎn)，以θ為根長(zhǎng)出的所有l(wèi)+1個(gè)頂點(diǎn)的數(shù)Tl+1所得的圖集，記為GT(θ,1)，當(dāng)Tl+1為星圖Kl+1，記所的圖為

引理2 對(duì)任一Gl∈GT(θ,1)，Gl與不同構(gòu)，有：

引理3 如果T為任一n階樹(shù)，那么對(duì)于任何一個(gè)正整數(shù)k，2≤k≤，存在V∈V(T)，使得|V'|=k-1，且T-V全部分支階樹(shù)都不超過(guò)

證 不妨設(shè)G是n階樹(shù)T添加一邊e=[μ,θ]而形成的，即G=T+e

由引理3可知，存在V∈(V(T)=V(G)，使|V'|=k-1，且T-V的所有分支的階數(shù)不超過(guò)，令T-V的所有分支為T(mén)1，T2，…,Ti，下面就e所在位置幾種情形討論.

情形1：μ∈V或θ∈V，則，T1，T2，…，Ti,就G-V的所有分支.從而(2.1)成立.

情形2：e在某分支T1中，則T1為單圈圖，[V(Ti)]≤，令T1=Ti，于是條件成立.

情形3：e作為割邊連接了T的某兩個(gè)分支，不妨設(shè)為T(mén)1，T2，令Ti=T1UT2U[e]則有

于是條件(3.3)成立,故，引理得證.

3 結(jié)果

證任意圈上的某點(diǎn)θ，記G'=G-θ，則G為n-1階森林.因此有：λk(G)≤λk-1(G')（引理1）

證畢.

圖1 Gt

易得：P(Gt,λ)=λ2t-4(λ4-(2t-1)λ2+(t-1)2)

證由引理5可知，存在V?V(G),|V|=k-1,使G-V的所有分支T1，T2，…，Tm滿足（2.1），（2.2），（2.3）之一，下面分幾種情形討論.

1）當(dāng)n≡0(modk)，且t≥1時(shí)，存在n階單圈圖G1，使λk

2）當(dāng)n≡0(modk)，且t≥2時(shí)，存在n階單圈圖G2，使λk

〔1〕于廣龍.有關(guān)組合矩陣論中圖譜與符號(hào)模式矩陣的研究[D].華東師范大學(xué),2011.

〔2〕田路路.簡(jiǎn)單連通圖的鄰接譜半徑的若干問(wèn)題的研究[D].華僑大學(xué),2013.

〔3〕李國(guó)君.關(guān)于圖的零度和無(wú)符號(hào)拉普拉斯譜半徑的研究[D].北京交通大學(xué),2014.

〔4〕扈生彪.單圈圖的最大特征值的上界的改進(jìn)(英文)[J].數(shù)學(xué)研究與評(píng)論,2009（05）:945-950.

O157.5

A

1673-260X（2017）01-0001-02

2016-10-10

石河子大學(xué)高層次人才科研啟動(dòng)資金專項(xiàng)(RCZX201418)；石河子大學(xué)應(yīng)用基礎(chǔ)研究青年項(xiàng)目(2015ZRKXYQLH09)