論單圈圖的特征值上界

馬志輝

（石河子大學 理學院，新疆 石河子 832000）

論單圈圖的特征值上界

馬志輝

（石河子大學 理學院，新疆 石河子 832000）

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

單圈圖；上界；特征值

1 引言

本文所研究的單圈圖是恰含一個圈的簡單連通圖，單圈圖G的特征值就是它的鄰接矩陣A(G)的特征值，A(G)的特征，多項式記為P(G,λ)，如果G是一個n階單圈圖，則A (G)是一個n階對稱(0,1)矩陣，故A(G)的第n個特征值，也就是G的第n個特征值全為實數，我們可以按遞降次序將它們排列為：

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

在沒有特別說明的情況下，本文的G均代表n階連通的單圈圖.

洪淵證明了：

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

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

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

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

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

3.當n=0(modk)，存在n階樹T*，使得：

本文在上述研究基礎上，對n階連通單圈圖G的第個特征值的上界問題證明了：

2 引理

引理1 柯西插入定理

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

證 設θ是G的非孤立點，以θ為根長出的所有l(wèi)+1個頂點的數Tl+1所得的圖集，記為GT(θ,1)，當Tl+1為星圖Kl+1，記所的圖為

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

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

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

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

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

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

情形3：e作為割邊連接了T的某兩個分支，不妨設為T1，T2，令Ti=T1UT2U[e]則有

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

3 結果

證任意圈上的某點θ，記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）當n≡0(modk)，且t≥1時，存在n階單圈圖G1，使λk

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

〔1〕于廣龍.有關組合矩陣論中圖譜與符號模式矩陣的研究[D].華東師范大學,2011.

〔2〕田路路.簡單連通圖的鄰接譜半徑的若干問題的研究[D].華僑大學,2013.

〔3〕李國君.關于圖的零度和無符號拉普拉斯譜半徑的研究[D].北京交通大學,2014.

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

O157.5

A

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

2016-10-10

石河子大學高層次人才科研啟動資金專項(RCZX201418)；石河子大學應用基礎研究青年項目(2015ZRKXYQLH09)