關于處處可斷圖類的最大譜半徑

武 建

(山西財經(jīng)大學 應用數(shù)學學院， 山西 太原 030006)

0 引 言

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

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

圖 1 11個個體之間的競爭-合作關系模型Fig.1 Competition-cooperation model with 11 individuals

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

h=n-2, h≥3.

本文未提及術語參見文獻[8].

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

1 預備知識

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

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

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

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

1) 頂點集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]導出頂點數(shù)為h的完全子圖；

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

6)G*[S1∩S2]為頂點數(shù)至少為1的完全子圖， 或空圖；

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

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

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

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

證明 設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的每個頂點均為割點. 這與引理1矛盾. 因而2≤h≤n-2， 且n≥4成立， 即結(jié)果(1)成立. 當n=4時， 即有結(jié)果(2)成立.

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

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

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

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

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

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

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

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

2.1 主要結(jié)果

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

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

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

2.2 定理1的證明

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

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

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

證明 設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. 因為在連通圖上添加邊可以使圖的譜半徑增大[21]， 所以當譜半徑達到最大時， 圖G的結(jié)構可由下面步驟得到： Step1.添加邊使得集合V(G){u1,u2}在新圖中導出一個完全子圖Kn-2； Step2.將頂點u1連接到集合V(Kn-2){v}的每個頂點； Step3. 將頂點u2連接到集合V(Kn-2){u}的每個頂點. 由構造可知， 當譜半徑達到最大時，G?G*. 命題得證.

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

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

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

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

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

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

證明 假設符號：N(u1)∩N(u2)={w}，N1=N(u1){u2,w},N2=N(u2)(u1,w}. 因為V(G)(N(u1)∪N(u2))≠φ， 所以|V(G)(N(u1)∪N(u2))|≥1成立. 由圖G的結(jié)構知， 頂點ui(i=1,2)與V(G)(N(u1)∪N(u2))中的點均不相鄰.

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

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

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

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

下面考慮當N(u1)∩N(u2)={p1,p2,…,pm}(m=2,3,…)的情形. 假設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))≠φ成立， 則譜半徑達到最大時，G?G*.

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

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

2) 當|N1∪N2|≥1時， 不妨設u∈N2. 當譜半徑達到最大時圖G的結(jié)構可由如下步驟得到： Step1.添加邊使得V(G){u1,p1}在新圖中導出一個完全子圖Kn-2； Step2.將頂點u1與集合V(Kn-2){u}中的每個頂點連接； Step3.將頂點u2與集合V(Kn-2){v}中的每個頂點連接. 可以驗證，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成立， 則譜半徑達到最大時，G?G*.

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

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

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

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

由于G′ ?G， 因而當譜半徑達到最大時，G′與G對應的極圖相同. 當譜半徑達到最大時， 圖G對應的極圖G*可由如下方法得到：

由情形1和情形2可得， 當其譜半徑達到最大時，G?G*.

2.3 定理2的證明

設圖G*的頂點集為V(G*)={u1,u2,v1,v2,…,vh}， 圖G*的一個Perron向量為X=(xu1,xu2,xv1,…,xvh}， 其中， 分量xui與ui(i=1,2)對應； 分量xvj與頂點vj(j=1,2,…,h)對應. 因為頂點vj1,vj2(j1,j2∈{2,3,…,h-1})有相同的鄰集, 所以xvj1=xvj2成立. 簡記xv2與頂點集{v2,v3,…,vh-1}中的每個頂點對應. 由于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.

因為圖G*包含圈， 所以圖G*的譜半徑ρ>2[9]. 解以上方程構成的方程組可得

xu1=xu2=xv1=xvh,

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

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

進一步求解得

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

命題得證.

3 結(jié) 論

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

[1]汪小帆, 李翔, 陳關榮. 網(wǎng)絡科學導論[M]. 北京： 高等教育版社, 2013.

[2]賈曉峰， 朱必文. 一類圖中的最大團[J]. 系統(tǒng)科學與數(shù)學, 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]. 太原科技大學學報, 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]. 太原： 太原理工大學, 2007.

[6]馬紅平. 關于連通圖斷片的一些結(jié)果[J]. 徐州師范大學學報 (自然科學版), 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]. 應用數(shù)學學報, 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]. 太原理工大學學報, 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.