武 建

(山西財(cái)經(jīng)大學(xué) 應(yīng)用數(shù)學(xué)學(xué)院， 山西 太原 030006)

0 引 言

圖作為研究復(fù)雜網(wǎng)絡(luò)的一種語言， 提供了用抽象的點(diǎn)和線表示各種實(shí)際網(wǎng)絡(luò)的一種方法[1]. 在經(jīng)濟(jì)政治全球化背景下， 各個(gè)個(gè)體間既充滿了競(jìng)爭(zhēng)的必然性又涌現(xiàn)出合作的可能性， 現(xiàn)實(shí)中存在很多競(jìng)爭(zhēng)與合作關(guān)系. 作為“競(jìng)爭(zhēng)-合作”關(guān)系的一種模型， 假設(shè)存在11個(gè)競(jìng)爭(zhēng)者， 且用字母A，B，C，D，E，F(xiàn)，G，H，I，J，K分別表示， 這里稱每個(gè)字母為一個(gè)頂點(diǎn). 若兩個(gè)競(jìng)爭(zhēng)者之間建立了直接且穩(wěn)定的合作關(guān)系， 則認(rèn)為這兩個(gè)個(gè)體之間建立了關(guān)系. 此時(shí)， 在兩個(gè)競(jìng)爭(zhēng)個(gè)體對(duì)應(yīng)的頂點(diǎn)間連一條線(稱其為邊)， 來表示他們之間這種關(guān)系的存在； 否則， 兩個(gè)頂點(diǎn)間不存在連線. 這11個(gè)個(gè)體之間的競(jìng)爭(zhēng)與合作關(guān)系模型如圖 1 所示. 該模型的一個(gè)顯著特點(diǎn)是： 每個(gè)頂點(diǎn)均處在至少一個(gè)極小割集中.

設(shè)G是連通圖， 若對(duì)于S?V(G)，GS是不連通的(指GS至少包含兩個(gè)連通分支)， 則稱S是G的一個(gè)割集. 若S是G的一個(gè)割集， 但S的任意真子集不是G的割集， 則稱S是G的一個(gè)極小割集. 設(shè)h≥2的正整數(shù)，S?V是圖G=(V,E)的極小割集. 若|S|≤h， 則稱極小割集S是一個(gè)下h-割集. 若對(duì)任意的頂點(diǎn)v∈V(G)均存在一個(gè)下h-割集S使得v∈S成立， 則稱圖G是一個(gè)處處h-可斷圖. 所有具有n個(gè)頂點(diǎn)的處處h-可斷圖構(gòu)成了一個(gè)新的圖類， 即處處可斷圖類， 記作H(h,n). 對(duì)處處可斷圖類的研究在集成電路布線等問題中有實(shí)際意義. 關(guān)于處處可斷圖類的進(jìn)一步研究見文獻(xiàn)[2-6].

圖 1 11個(gè)個(gè)體之間的競(jìng)爭(zhēng)-合作關(guān)系模型Fig.1 Competition-cooperation model with 11 individuals

最小(邊)割集覆蓋問題是與處處可斷圖類研究相關(guān)的一類重要問題[7]. 處處可斷圖類的研究條件是每個(gè)頂點(diǎn)都處在至少一個(gè)極小頂點(diǎn)割集中. 從圖的對(duì)偶性角度來看， 對(duì)該類圖的研究有重要意義， 圖譜理論是圖論研究的重要領(lǐng)域之一. 本文討論了處處可斷圖類的最大鄰接譜半徑問題， 并且構(gòu)造了處處可斷圖類譜半徑達(dá)到最大時(shí)的極圖G*(見圖 2). 同時(shí)， 給出了處處可斷圖類最大譜半徑的一個(gè)確切的上界，

h=n-2, h≥3.

本文未提及術(shù)語參見文獻(xiàn)[8].

圖 2 極圖G*Fig.2 The extremal graph G*

1 預(yù)備知識(shí)

設(shè)A(G)是圖G的鄰接矩陣. 顯然， 矩陣A(G)是實(shí)對(duì)稱(0,1)矩陣， 其特征值均為實(shí)數(shù). 圖G的譜半徑, 記作ρ, 是圖G的鄰接矩陣A(G)的最大特征根. 由Perron-Frobenius定理知， 譜半徑是矩陣A(G)的單根， 且對(duì)應(yīng)一個(gè)正的特征向量， 該向量被稱為圖G的Perron向量[9]. 本文依據(jù)圖的頂點(diǎn)劃分， 研究了處處可斷圖類的最大譜半徑問題. 圍繞Brualdi等[9]提出的關(guān)于確定給定圖類譜半徑上界的問題, 圖的譜半徑研究受到了廣泛關(guān)注[10-12]. 文獻(xiàn)[13-15] 對(duì)含有割邊、 有割點(diǎn)的兩類圖的譜半徑進(jìn)行了研究. 關(guān)于圖的譜半徑研究的新熱點(diǎn)見文獻(xiàn)[16-17]. 文獻(xiàn)[18-19]以病毒傳播網(wǎng)絡(luò)為研究背景， 研究了在給定圖的直徑下圖的最大譜半徑和最小譜半徑.

對(duì)任意的圖G， 本文用N(v)表示頂點(diǎn)v∈V(G)的鄰集， 用G[A]表示由集合A?V(G)導(dǎo)出的子圖. 圖G的最大完全子圖所包含的頂點(diǎn)數(shù)為圖的最大團(tuán)數(shù)， 記作ω(G)[20]. 設(shè)G∈H(h,n)， 圖G的可斷數(shù)為

S?V(G)是圖G的極小割集}.

通過參數(shù)h(G)和ω(G)， 本文構(gòu)造了處處可斷圖類譜半徑達(dá)到最大時(shí)的極圖G*(見圖 2)：

1) 頂點(diǎn)集V(G*)={u1,u2,v1,v2,…,vh}；

2)S1={v1,v2,…,vh-1}，S2={v2,v3,…,vh}；

3)S=S1∪S2，S1∩S2={v2,v3,…,vh-1}；

4)G*[S]導(dǎo)出頂點(diǎn)數(shù)為h的完全子圖；

5)G*[S1],G*[S2]均導(dǎo)出頂點(diǎn)數(shù)為h-1的完全子圖；

6)G*[S1∩S2]為頂點(diǎn)數(shù)至少為1的完全子圖， 或空?qǐng)D；

7)N(u1){u2}=S1，N(u2){u1}=S2.

引理 1 任意一個(gè)非平凡且無環(huán)的連通圖至少包含兩個(gè)不為割點(diǎn)的頂點(diǎn).

引理 2[4]S?V(G)是圖G的極小割集的充要條件是對(duì)任意的頂點(diǎn)u∈S及連通分支G-S(記作G[A]或〈A〉)， 有N(u)∩A≠φ成立.

引理 3 若圖G∈H(h,n)， 則： (1)2≤h≤n-2且n≥4； (2) 圈C4是最小的處處可斷圖.

證明 設(shè)G∈H(h,n)， 則圖G的階數(shù)為n(>h). 若S?V(G)是圖G的極小割集， 且|S|=h=n-1， 則G-S連通分支數(shù)為1. 這與S是圖G的極小割集矛盾. 因此，h≤n-2成立. 若h<2， 則h=1. 于是， 圖G的每個(gè)頂點(diǎn)均為割點(diǎn). 這與引理1矛盾. 因而2≤h≤n-2， 且n≥4成立， 即結(jié)果(1)成立. 當(dāng)n=4時(shí)， 即有結(jié)果(2)成立.

引理 4[4]若G∈H(h,n)，v∈G是圖G的割點(diǎn)， 則G-v的每個(gè)連通分支至少有4個(gè)頂點(diǎn).

引理 5 若G∈H(h,n)， 則圖G的最小度δ滿足δ≥2 .

證明 設(shè)G∈H(h,n)， 頂點(diǎn)v∈G的度為1， 則其鄰接頂點(diǎn)u必為割點(diǎn). 于是， 必有G-u的一個(gè)連通分支只含有唯一的一個(gè)頂點(diǎn)v. 這與引理4矛盾.

由引理5可得如下結(jié)論.

推論 1 若G∈H(h,n)， 則圖G必定包含一個(gè)長至少為3的圈.

設(shè)頂點(diǎn)v∈G. 如果頂點(diǎn)v的鄰集N(v)的導(dǎo)出子圖是一個(gè)完全圖， 那么稱頂點(diǎn)v是圖G的一個(gè)完全頂點(diǎn). 下面的結(jié)論說明處處可斷圖不包含完全頂點(diǎn).

引理 6[2]若G∈H(h,n)， 圖G不包含完全頂點(diǎn).

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

2.1 主要結(jié)果

本節(jié)刻畫了處處可斷圖類譜半徑達(dá)到最大時(shí)的極圖， 并計(jì)算了極圖的譜半徑.

定理 1 若圖G∈H(h,n)， 則當(dāng)其譜半徑達(dá)到最大時(shí)，G?G*.

由定理 1 和定理 2 可得處處可斷圖類譜半徑的上界.

2.2 定理1的證明

設(shè)圖G∈H(h,n)， 由引理5知， 圖G不包含1度頂點(diǎn). 進(jìn)而, 對(duì)任意的頂點(diǎn)v∈V(G)， 其鄰集必然滿足|N(v)|≥2. 不失一般性， 設(shè)u1,u2是圖G的兩個(gè)頂點(diǎn)， 且邊u1u2∈E(G). 為了方便刻畫極圖結(jié)構(gòu)， 下面給出一些符號(hào)：N(u1),N(u2)分別表示頂點(diǎn)u1,u2的鄰集；N(u1)∪N(u2)，N(u1)∩N(u2) 分別表示集合N(u1),N(u2)的并和交；N(u1){u2}，N(u2){u1}，V(G){u1,u2}，V(G)(N(u1)∪N(u2))均表示從點(diǎn)集中刪除一個(gè)或一些點(diǎn)后得到的集合. 下面根據(jù)頂點(diǎn)u1,u2的鄰集來劃分圖的頂點(diǎn)， 分兩種情況， 利用若干命題完成定理的證明.

情況 1N(u1)∩N(u2)=φ.

命題 1 若N(u1)∩N(u2)=φ， 且有|N(u1){u2}|=|N(u2){u1}|=1成立， 則譜半徑達(dá)到最大時(shí)，G?G*.

證明 設(shè)N(u1){u2}={u}，N(u2){u1}={v}.

1) 若V(G)(N(u1)∪N(u2))=φ， 圖G?C4. 否則， 圖G不是處處可斷圖.

2) 若V(G)(N(u1)∪N(u2))≠φ, 則|V(G)(N(u1)∪N(u2))|≥1. 因?yàn)樵谶B通圖上添加邊可以使圖的譜半徑增大[21]， 所以當(dāng)譜半徑達(dá)到最大時(shí)， 圖G的結(jié)構(gòu)可由下面步驟得到： Step1.添加邊使得集合V(G){u1,u2}在新圖中導(dǎo)出一個(gè)完全子圖Kn-2； Step2.將頂點(diǎn)u1連接到集合V(Kn-2){v}的每個(gè)頂點(diǎn)； Step3. 將頂點(diǎn)u2連接到集合V(Kn-2){u}的每個(gè)頂點(diǎn). 由構(gòu)造可知， 當(dāng)譜半徑達(dá)到最大時(shí)，G?G*. 命題得證.

運(yùn)用與命題1類似的證明過程(2)可得如下結(jié)論.

命題 2 若N(u1)∩N(u2)=φ， 且有|N(u1){u2}|=1, |N(u2){u1}|≥成立， 則譜半徑達(dá)到最大時(shí)，G?G*.

命題 3 若N(u1)∩N(u2)=φ， 且有|N(u2){u1}|=1, |N(u1){u2}|≥2成立， 則譜半徑達(dá)到最大時(shí)，G?G*.

命題 4 若N(u1)∩N(u2)=φ， 且有|N(u1){u2}|≥2, |N(u2){u1}|≥2成立， 則譜半徑達(dá)到最大時(shí)，G?G*.

情況 2N(u1)∩N(u2)≠φ.

命題 5 若N(u1)∩N(u2)≠φ， 且有|N(u1)∩N(u2)|=1,V(G)(N(u1)∪N(u2)≠φ成立， 則譜半徑達(dá)到最大時(shí)，G?G*.

證明 假設(shè)符號(hào)：N(u1)∩N(u2)={w}，N1=N(u1){u2,w},N2=N(u2)(u1,w}. 因?yàn)閂(G)(N(u1)∪N(u2))≠φ， 所以|V(G)(N(u1)∪N(u2))|≥1成立. 由圖G的結(jié)構(gòu)知， 頂點(diǎn)ui(i=1,2)與V(G)(N(u1)∪N(u2))中的點(diǎn)均不相鄰.

若|Ni|=0(i=1,2)， 則ui(i=1,2)構(gòu)成圖G的一個(gè)完全頂點(diǎn). 這與引理6矛盾. 所以， 必有|Ni|≥1(i=1,2)成立. 設(shè)w1∈N1，w2∈N2， 則當(dāng)譜半徑達(dá)到最大時(shí)， 圖G的結(jié)構(gòu)如下： Step1.添加邊使得集合V(G){u1,u2}在新圖中導(dǎo)出一個(gè)完全子圖Kn-2； Step2.將頂點(diǎn)u1連接到集合V(G)(N(u1)∪N(u2))包含的每個(gè)頂點(diǎn)； Step3.將頂點(diǎn)u1連接到集合N2{w2}包含的頂點(diǎn)； Step4.將頂點(diǎn)u2連接到集合V(G)(N(u1)∪N(u2))包含的每個(gè)頂點(diǎn)； Step5. 將頂點(diǎn)u2連接到集合N1{w1}包含的頂點(diǎn). 特別地， 若Ni{wi}=φ(i=1,2)時(shí), 則不添加邊. 由構(gòu)造可知， 當(dāng)譜半徑達(dá)到最大時(shí),G?G*. 命題得證.

命題 6 若N(u1)∩N(u2)≠φ， 且有|N(u1)∩N(u2)|=1,V(G)(N(u1)∪N(u2))=φ成立， 則譜半徑達(dá)到最大時(shí)，G?G*.

證明 假設(shè)符號(hào)：N(u1)∩N(u2)={w}，N1=N(u1){u2,w}，N2=N(u2){u1,w}， 則必有|Ni|≥1(i=1,2)成立. (如若不然， 假設(shè)|N1|=0. 因?yàn)閂(G)(N(u1)∪N(u2))=φ， 且頂點(diǎn)u1與集合N2中的頂點(diǎn)均不相鄰, 所以G[N(u1)]在圖G中導(dǎo)出一個(gè)完全子圖. 這與引理6矛盾. )

設(shè)w1∈N1，w2∈N2, 則當(dāng)譜半徑達(dá)到最大時(shí)圖G結(jié)構(gòu)如下： Step1. 添加邊使得集合V(G){u1,u2}在新圖中導(dǎo)出一個(gè)完全子圖Kn-2， 這里V(G){u1,u2}=N1∪N2∪{w}； Step2. 將頂點(diǎn)u1與集合N2{w2}包含的每個(gè)頂點(diǎn)連接， 特別地, 若N2{w2}=φ則不添加任何邊； Step3. 將頂點(diǎn)u2與集合N1{w1}包含的每個(gè)頂點(diǎn)連接， 特別地， 若N1{w1}=φ則不添加任何邊； 可以驗(yàn)證，G?G*. 命題得證.

下面考慮當(dāng)N(u1)∩N(u2)={p1,p2,…,pm}(m=2,3,…)的情形. 假設(shè)N1=N(u1){u2,p1,p2,…,pm}，N2=N(u2){u1,p1,p2,…,pm}.

命題 7 若N(u1)∩N(u2)≠φ， 且有|N(u1)∩N(u2)|=m(m=2,3,…),V(G)(N(u1)∪N(u2))≠φ成立， 則譜半徑達(dá)到最大時(shí)，G?G*.

證明 設(shè)v∈V(G)(N(u1)∪N(u2))， 則必有u1與N2中的點(diǎn)不相鄰；u2與N1中的點(diǎn)不相鄰；v與頂點(diǎn)ui(i=1,2)不相鄰； |N1∪N2|=0或|N1∪N2|≥1成立.

1) 當(dāng)|N1∪N2|=0時(shí)， 若G[{p1,p2,…,pm}]導(dǎo)出完全子圖， 則圖G包含完全頂點(diǎn)， 與引理6矛盾. 因此， {p1,p2,…,pm}中必然包含兩個(gè)不相鄰頂點(diǎn). 不妨設(shè)p1p2?E(G). 于是， 當(dāng)譜半徑達(dá)到最大時(shí)圖G的結(jié)構(gòu)可由如下步驟得到： Step1.添加邊使得V(G){u1,p1}在新圖中導(dǎo)出一個(gè)完全子圖Kn-2； Step2.將頂點(diǎn)u1與集合V(Kn-2){v}中的每個(gè)頂點(diǎn)連接； Step3.將頂點(diǎn)p1與集合V(Kn-2){p2}中的每個(gè)頂點(diǎn)連接. 可以驗(yàn)證，G?G*.

2) 當(dāng)|N1∪N2|≥1時(shí)， 不妨設(shè)u∈N2. 當(dāng)譜半徑達(dá)到最大時(shí)圖G的結(jié)構(gòu)可由如下步驟得到： Step1.添加邊使得V(G){u1,p1}在新圖中導(dǎo)出一個(gè)完全子圖Kn-2； Step2.將頂點(diǎn)u1與集合V(Kn-2){u}中的每個(gè)頂點(diǎn)連接； Step3.將頂點(diǎn)u2與集合V(Kn-2){v}中的每個(gè)頂點(diǎn)連接. 可以驗(yàn)證，G?G*. 由1), 2)知， 命題得證.

命題 8 若N(u1)∩N(u2)≠φ， 且有|N(u1)∩N(u2)|=m(m=2,3,…)，V(G)(N(u1)∪N(u2))=φ， |N1∪N2|≥1成立， 則譜半徑達(dá)到最大時(shí)，G?G*.

證明 下面分1)|Ni|=0, |Nj|≥1,i=1,2， 且i≠j； 2)|Nk|≥1,k=1,2， 兩種情形完成證明.

若1)成立， 設(shè)|N1|=0, |N2|≥1， 且v∈N2， 則根據(jù)引理6， {p1,p2,…,pm}中必然包含兩個(gè)不相鄰頂點(diǎn). 不妨設(shè)p1p2?E(G). 當(dāng)譜半徑達(dá)到最大時(shí)圖G的結(jié)構(gòu)可由如下步驟得到： Step1.添加邊使得v(G){u1,p1}在新圖中導(dǎo)出一個(gè)完全子圖Kn-2； Step2.將頂點(diǎn)u1與集合V(Kn-2){v}中的每個(gè)頂點(diǎn)連接； Step3.將頂點(diǎn)p1與集合V(Kn-2){p2}中的每個(gè)頂點(diǎn)連接. 可以驗(yàn)證，G?G*.

若2)成立， 不妨設(shè)q1∈N1，q2∈N2, 則當(dāng)譜半徑達(dá)到最大時(shí)圖G的結(jié)構(gòu)可由如下步驟得到： Step1.添加邊使得V(G){u1,u2}在新圖中導(dǎo)出一個(gè)完全子圖Kn-2； Step2.將頂點(diǎn)u1與集合N2{q2}中的每個(gè)頂點(diǎn)連接； Step3.將頂點(diǎn)u2與集合N1{q1}中的每個(gè)頂點(diǎn)連接. 可以驗(yàn)證，G?G*. 通過對(duì)1), 2)的分析， 命題得證.

命題 9 若N(u1)∩N(u2)≠φ， 且有|N(u1)∩N(u2)|=m(m=2,3,…),V(G)(N(u1)∪N(u2))=φ, |N1∪N2|=0成立， 則譜半徑達(dá)到最大時(shí)，G?G*.

由于G′ ?G， 因而當(dāng)譜半徑達(dá)到最大時(shí)，G′與G對(duì)應(yīng)的極圖相同. 當(dāng)譜半徑達(dá)到最大時(shí)， 圖G對(duì)應(yīng)的極圖G*可由如下方法得到：

由情形1和情形2可得， 當(dāng)其譜半徑達(dá)到最大時(shí)，G?G*.

2.3 定理2的證明

設(shè)圖G*的頂點(diǎn)集為V(G*)={u1,u2,v1,v2,…,vh}， 圖G*的一個(gè)Perron向量為X=(xu1,xu2,xv1,…,xvh}， 其中， 分量xui與ui(i=1,2)對(duì)應(yīng)； 分量xvj與頂點(diǎn)vj(j=1,2,…,h)對(duì)應(yīng). 因?yàn)轫旤c(diǎn)vj1,vj2(j1,j2∈{2,3,…,h-1})有相同的鄰集, 所以xvj1=xvj2成立. 簡(jiǎn)記xv2與頂點(diǎn)集{v2,v3,…,vh-1}中的每個(gè)頂點(diǎn)對(duì)應(yīng). 由于A(G*)X=ρX， 所以如下方程成立，

ρxu1=xu2+xv1+(h-2)xv2,

ρxu2=xu1+xvh+(h-2)xv2,

ρxv1=xu1+xvh+(h-2)xv2,

ρxvh=xu2+xv1+(h-2)xv2,

ρxv2=xu1+xu2+xv1+xvh+(h-3)xv2.

因?yàn)閳DG*包含圈， 所以圖G*的譜半徑ρ>2[9]. 解以上方程構(gòu)成的方程組可得

xu1=xu2=xv1=xvh,

ρxu1=2xu1+(h-2)xv2,

ρxv2=4xu1+(h-3)xv2.

進(jìn)一步求解得

ρ2-2ρ-5h+11=0,

命題得證.

3 結(jié) 論

任意一個(gè)圖均可看作某個(gè)處處可斷圖的子圖. 在理論上， 可用處處可斷圖來估計(jì)其它圖的譜半徑的界和其它參數(shù)的界. 作為一種解決問題的方法， 結(jié)果具有重要的理論意義. 沒有建立有效的算法來構(gòu)造處處可斷圖類， 并深入討論該圖類的代數(shù)結(jié)構(gòu)是結(jié)果的不足之處， 也是有待改進(jìn)的方面.

[1]汪小帆, 李翔, 陳關(guān)榮. 網(wǎng)絡(luò)科學(xué)導(dǎo)論[M]. 北京： 高等教育版社, 2013.

[2]賈曉峰， 朱必文. 一類圖中的最大團(tuán)[J]. 系統(tǒng)科學(xué)與數(shù)學(xué), 1988, 8(3)： 226-233. Jia Xiaofeng, Zhu Biwen. The maximum clique in an everywhere separable graph[J]. Journal of System Science and Mathematical Science Chinese Series, 1988, 8(3)： 226-233. (in Chinese)

[3]武建, 賈曉峰, 孫立新. 一類圖的可加邊問題[J]. 太原科技大學(xué)學(xué)報(bào), 2006, 27(6)： 495-500. Wu Jian, Jia Xiaofeng, Sun Lixin. The additive edge prpblem in separable graph[J]. Journal of Taiyuan University of Science and Tehcnology, 2006, 27(6)： 495-500. (in Chinese)

[4]Jia X F. Some results concerning the ends of minimal cuts of simple graphs[J]. Discussiones Mathematicae, 2000, 20(1)： 139-142.

[5]武建. 處處可斷圖的若干問題研究[D]. 太原： 太原理工大學(xué), 2007.

[6]馬紅平. 關(guān)于連通圖斷片的一些結(jié)果[J]. 徐州師范大學(xué)學(xué)報(bào) (自然科學(xué)版), 2005, 23(2)： 19-21. Ma Hongping.Some results of about the ends of connected graphs[J]. Journal of Xuzhou Normal University (Natural Science Edition), 2005, 23(2)： 19-21. (in Chinese)

[7]Hoshino E A. The minimum cut cover problem[J]. Electronic Notes in Discrete Mathematics, 2011, 37： 255-260.

[8]Bondy J A, Murty U S R. Graph theory with applications[M]. London: Macmillan, 1976.

[9]Bruadli R A, Solheid E S. On the spectral radius of complementary acyclic matrices of zeros and ones[J]. SIAM Journal on Algebra Discrete Methods, 1986, 7(2)： 265-272.

[10]李喬, 馮克勤. 論圖的最大特征根[J]. 應(yīng)用數(shù)學(xué)學(xué)報(bào), 1979, 2(2)： 167-175. Li Qiao, Feng Keqin. On the largest eigenvalue of graphs[J]. Acta Mathematicae Applicatae Sinica, 1979, 2(2)： 167-175. (in Chinese)

[11]Cvetkovi D, Simi S. Graph spectra in computer science[J]. Linear Algebra and Its Applications, 2011, 434(6)： 1545-1562.

[12]Hansen P, Stevanovi D. On bags and bugs[J]. Discrete Applied Mathematics, 2008, 156(7)： 986-997.

[13]Liu H Q, Lu M, Tian F. On the spectral radius of graphs with cut edges[J]. Linear Algebra and Its Applications, 2004, 389(1)： 139-145.

[14]Berman A, Zhang X D. On the spectral radius of graphs with cut vertices[J]. Journal of Combinatorial Theory Series B, 2001, 83(2)： 233-240.

[15]武建. 一類圖的譜半徑[J]. 太原理工大學(xué)學(xué)報(bào), 2010, 41(3)： 320-322. Wu Jian. The spectral radius on a class of graphs[J]. Journal of Taiyuan University of Technology, 2010, 41(3)： 320-322. (in Chinese)

[16]Tian X G, Wang L G, Lu Y. On the second smallest and the largest normalized Laplacian eigenvalues of a graph[EB/OL]. [2017-06-10]. http：∥120.52.73.76/arxiv.org/pdf/1603.04301.pdf.

[17]Lin H Y, Zhou B. Distance spectral radius of uniform hypergraphs[EB/OL]. [2017-06-09]. http：∥120.52.73.78/arxiv.org/pdf/1602.08214.pdf.

[18]Van Dam E R. Graphs with given diameter maximizing the spectral radius[J]. Linear Algebra and Its Applications, 2007, 426(2/3)： 454-457.

[19]Van Dam E R, Kooij R E. The minimal spectral radius of graphs with a given diameter[J]. Linear Algebra and Its Applications, 2007, 423(2/3)： 408-419.

[20]Yuan X Y, Shao J Y, Liu Y. The minimal spectral radius of graphs of order n with diameter n-4[J]. Linear Algebra and Its Applications, 2008, 428(11/12)： 2840-2851.

[21]Cvetkovi D M, Doob M, Sachs H. Spectra of graphs[M]. Third Ed. Heidelberg-Leipzig: Johann Abrosius Barth Verlag, 1995.