陳明珠,張曉東

(上海交通大學 數學科學學院,教育部科學工程計算重點實驗室,上海 200240)

論文系統(tǒng)介紹譜極值圖論的最新研究成果、進展以及相關問題.主要內容含有各種Turán類型，包括完全子圖、線性森林、圈、二部圖以及圖子式等鄰接譜和無符號拉普拉斯譜的最新研究成果，同時介紹該領域的尚未解決的猜想和相關問題.

Turán類型問題；禁用子圖；譜半徑；無符號拉普拉斯譜半徑

論文考慮的圖都是有限無向簡單圖.令G=(V(G),E(G))是一個簡單圖，其中V(G)為頂點集，E(G)為邊集.用e(G)表示圖G的邊數.給定兩個點無交的簡單圖G和H,G∪H表示G和H的不交并.kG表示k個同構圖G的不交并，G∨H表示由G∪H通過添加所有的連接G中的點和H中的點的邊而得到的圖.線性森林指的是幾條不交路的并.如果一個圖H能從圖G中通過刪邊、收縮邊或者刪點得到，那么稱H是圖G的H-子式，反之，稱圖G不含H-子式.

圖G的鄰接矩陣A(G)是n×n矩陣(aij), 如果vi和vj鄰接，則aij=1, 否則為0.圖G的無符號拉普拉斯矩陣Q(G)是n×n矩陣(qij), 其中對角元素qii為頂點i的度，對于非對角元素，如果vi和vj鄰接，則qij=1, 否則為0.易知，圖G的鄰接矩陣A(G)和無符號拉普拉斯矩陣Q(G)的特征值都是實數.圖G的譜半徑就是它的鄰接矩陣A(G)的最大特征值，記為ρ(G).圖G的無符號拉普拉斯譜半徑就是它的無符號拉普拉斯矩陣Q(G)的最大特征值，記為q(G).

1 Turán類型極值圖論問題

譜極值圖論問題主要研究與圖相伴隨的各種矩陣，包括鄰接矩陣、拉普拉斯矩陣或無符號拉普拉斯矩陣等的譜性質，特別是關于不含有特殊子結構的圖類中譜半徑或者其他特征值和特征向量，例如Stanley界[4]和Wilf定理[5].其中最典型的就是Nikiforov[6]在2010年提出的譜Turán類型極值問題：求不包含給定的圖H作為子圖的所有n個頂點的圖的最大譜半徑.稍作變形，可得另外一個典型的譜Turán類型極值問題：求不包含給定的圖H作為子圖的所有n個頂點的圖的最大無符號拉普拉斯譜半徑.很多典型的Turán類型極值問題的譜版本也成立.

論文主要介紹的是譜Turán類型極值問題的一些主要最新研究結果、最新進展以及相關問題和猜想.全文安排如下：第二部分介紹譜Turán定理(禁用完全子圖)；第三部分介紹禁用線性森林的譜Turán類型極值問題；第四部分介紹禁用圈的譜Turán類型極值問題；第五部分介紹禁用完全二部圖的譜Turán類型極值問題，也就是Zarankiewicz譜Turán類型極值問題；第六部分介紹禁用圖子式的譜Turán類型極值問題.

2 譜Turán定理

2.1 鄰接譜Turán定理

Wilf[5]在1986年利用圖的頂點數和團數，給出了圖的譜半徑的上界.

定理1[5]令G是一個頂點數為n的簡單圖.若G的團數為ω(G)=ω, 則

ρ(G)≤(1-1/w)n.

令函數f(x)=(1-1/x)n(其中n為正常數).當x>0時，f是增函數，則定理1等價于定理2.

定理2 令G是一個頂點數為n的簡單圖.若G不含Kr+1作為子圖，則

ρ(G)≤(1-1/r)n.

然而，只有r整除n的時候,定理2中不等式的等號才能成立.因此定理2中的界不是最優(yōu)的.實際上，Nikiforv[7]在2007年改進了定理2，得到了譜Turán定理.Guiduli[8]也證明了相同的結果.

定理3[7-8]令G是一個頂點數為n的簡單圖.若G不含Kr+1作為子圖，則

ρ(G)≤ρ(Tn,r),

等號成立當且僅當G=Tn,r.

實際上，定理3也改進了定理1，它等價于定理4.

定理4 令G是一個頂點數為n的簡單圖.若G的團數為ω(G)=ω, 則

ρ(G)≤ρ(Tn,ω),

等號成立當且僅當G=Tn,ω.

利用不等式ρ(G)≥2e(G)/n, 定理3可以推出經典的Turán定理.

推論1[3]令G是一個頂點數為n的簡單圖.若G不含Kr+1作為子圖，則

e(G)≤e(Tn,r),

等號成立當且僅當G=Tn,r.

若G沒有孤立點,則等號成立當且僅當下列兩種情況之一成立：

(i) r=2而且G是完全二部圖;

(ii) r≥3而且G是正則完全r-部圖.

實際上，Nikiforov[10-11]還得到了下列推論，證明Edward等[13]在1983年提出的猜想即推論2.

推論2[10]令G是一個頂點數為n的簡單圖.若G的團數為ω(G)=ω, 則

若G沒有孤立點,則等號成立當且僅當下列兩種情況之一成立：

(i)ω=2而且G是完全二部圖;

(ii)ω≥3而且G是正則完全ω-部圖.

定理6[11]令G是一個頂點數為n的簡單圖.若G的團數為ω(G)=ω, 則

若G沒有孤立點,k≥1, 則等號成立，則

(i) 若k=1,則G是正則完全ω-部圖;

(ii) 若k≥2和ω>2, 則G是正則完全ω-部圖;

(iii) 若k≥2和ω=2, 則G是完全二部圖.若k是奇數,則G是正則完全二部圖.

2.2 譜半徑和獨立數

ρ(G)≥n/α-1.

實際上，譜半徑和獨立數滿足下列更精確的結果如下：

定理7[14]令G是一個頂點數為n的簡單圖.若G的獨立數為α, 則

從資金規(guī)模來看，2017年，全國創(chuàng)投管理資本總量達到8 872.5億元，較2016年增加595.4億元，增幅為7.2%，較前兩年明顯放緩（見圖2）。此外，基金兩極分化的“杠鈴”現象進一步顯現② 兩極分化現象是各國發(fā)展的共同特征，如2017年美國創(chuàng)投統(tǒng)計數據顯示，管理資金超過10億美元的機構數量，從2016年的68家增加到83家，占比8.6%；管理資金小于2 500萬美元的機構數量，從2016年的241家增加到2017年的427家，占當年比重的44%。，管理資本規(guī)模超過5億元的機構雖然僅占10.2%，但掌握了72.1%的管理資本總量。

定理8[16]令G是一個獨立數為α的頂點數為n=kα的簡單連通圖.若α=3,4, 則

ρ(G)≥ρ(Pn,α),

其中：圖Pn,α是把一條長為α-1的路中每個頂點被k的團取代并且有2α-2個割點所得到的簡單圖.

最近Jin等[17]進一步考慮一般情形，并且推廣他們的結果.

定理9[17]令G是一個獨立數為α的頂點數為n=kα的簡單連通圖.若k>(17α+15)/8, 則

ρ(G)≥ρ(Pn,α),

其中：圖Pn,α是把一條長為α-1的路中每個頂點被k的團取代并且有2α-2個割點所得到的簡單圖，等號成立當且僅當G是Pn,α.

顯然上面定理并沒有完全刻畫獨立數為α的n個頂點的簡單連通圖中具有最小譜半徑的所有極圖，這是一個非常有趣的問題.

2.3 無符號拉普拉斯譜Turán定理

Abreu等[18]在2013年研究給定頂點數和團數的簡單圖的無符號拉普拉斯譜半徑，證明了Hansen等[19]在2009年提出的猜想.

定理10[18]令G是一個頂點數為n的簡單圖.若G的團數為ω(G)=ω, 則

q(G)≤2(1-1/w)n.

類似于定理1等價于定理2，定理10也等價于以下定理：

定理11 令G是一個頂點數為n的簡單圖.若G不含Kr+1作為子圖，則

q(G)≤2(1-1/r)n.

He等[20]在2013年也研究給定頂點數和團數的簡單圖，給出了這類圖的無符號拉普拉斯譜半徑的緊的上界，并刻畫了極圖.

定理12[20]令G是一個頂點數為n的簡單圖.若G的團數為ω(G)=ω≥2, 則

其中:n=kω+s, 0≤s<ω.

另外，等號成立當且僅當下面情況之一成立：

(i)ω=2且G是完全二部圖;

(ii)ω≥3,G=Tn,ω.

定理12等價于定理13.

定理13[20]令r≥2和G是一個頂點數為n的簡單圖.若G不含Kr+1作為子圖，則

其中:n=kr+s, 0≤s

另外，等號成立當且僅當下面情況之一成立：

(i)r=2且G是完全二部圖;

(ii)r≥3且G=Tn,r.

利用不等式q(G)≥4e(G)/n, 定理13可以推出經典的Turán定理.

推論3[3]令r≥3和G是一個頂點數為n的簡單圖.若G不含Kr+1作為子圖，則

e(G)≤e(Tn,r),

等號成立當且僅當G=Tn,r.

若r≥3, 定理3、13的極圖是一致的.但是當r=2, 定理3的極圖是唯一的，而定理13的極圖卻不是唯一的.這是因為完全二部圖的無符號拉普拉斯譜半徑就是它的頂點數.這說明鄰接譜極圖和無符號拉普拉斯譜極圖并不定是完全一致的.

3 禁用線性森林的譜Turán類型極值問題

Erd?s等[21]在1959年給出了不含給定長度的路作為子圖的簡單圖的最大邊數.

定理14[21]令h≥2和G是一個頂點數為n的簡單圖.若G不含Ph作為子圖，則

e(G)≤(h-2)n/2,

等號成立當且僅當G是頂點數為h-1的完全圖的不交并.

注意到若Erd?s-Gallai定理[21]中的等號成立，則h-1整除n, 也就是說若h-1不能整除n, Erd?s-Gallai定理還不是最優(yōu)的.他們的結果已陸續(xù)得到改進，如定理15.

定理15[22]令h≥1和G是一個頂點數為n>(5h+4)/2的簡單連通圖，則

(1) 若G不含P2h+2作為子圖，則e(G)≤e(Sn,h),等號成立當且僅當G=Sn,h；

Erd?s-Gallai[21]定理，即如果簡單圖G的平均度超過h-2, 則G包含Ph作為子圖.下列著名的Erd?s-Sós猜想[23]是Erd?s-Gallai定理[21]的推廣.

猜想1[23]令h≥2.如果簡單圖G的平均度超過h-2, 則G包含所有頂點數為h的樹作為子圖.

Erd?s-Sós猜想自提出以來一直受到很大的關注.對于很多給定的特殊的樹類，特別是直徑最多為4的樹[24]，其對應的Erd?s-Sós猜想已經被證明是正確的.關于該方面的進展可以參考文[25-26]以及后面的參考文獻.近年，Ajtai等利用正則引理給出了對于k充分大的Erd?s-Sós猜想的證明.

線性森林是幾條路的不交并.對于l≥3和頂點數n充分大，Bushaw等[27]給出了不含kPl作為子圖的簡單圖的最大邊數，并刻畫了極圖.Lidick等[28]把 Bushaw-Kettle結果拓展到了任意的頂點數充分大的線性森林.

(i) 若k≥1, 則e(G)≤e(Sn,h), 等號成立當且僅當G=Sn,h;

關于F=lP3, Yuan等[29]刻畫了對應所有極圖.

定理17[29]令F=lP3和G是一個頂點數為n的簡單圖.若G不含F作為子圖，則

(i) 當n<3k時，e(G)≤n(n-1)/2;

并且刻畫了所有的極圖.

3.1 禁用線性森林的鄰接譜Turán類型極值問題

類似于譜Turán定理，自然會問如果定理15的邊數換為譜半徑，結論是否成立？ 實際上，Nikiforov[6]在2010年給出了肯定的答案.

定理18[6]令h≥1和G是一個頂點數為n≥24h的簡單圖,則

(i) 若G不含P2h+2作為子圖，則ρ(G)≤ρ(Sn,h),等號成立當且僅當G=Sn,h；

另外， Zhai等[30]研究不含給定長度的路作為子圖的二部圖，并給出了最大譜半徑和刻畫了極圖.

根據著名的Erd?s-Sós猜想[23]，Nikiforov[6]提出了比定理18更為一般化猜想，即猜想2.

猜想2[6]令h≥2和G是一個頂點數為n充分大的簡單圖，則

(1) 若G不含某頂點數為2h+2的樹作為子圖，則ρ(G)≤ρ(Sn,h),等號成立當且僅當G=Sn,h；

定理18實際上證明了猜想2中的樹為路的情況.

回到線性森林的問題上，指出定理16對應的譜半徑版本也成立，而它的證明幾乎可以把定理18的證明移植過來.

(i) 若k≥1, 則ρ(G)≤ρ(Sn,h), 等號成立當且僅當G=Sn,h；

3.2 禁用線性森林的無符號拉普拉斯譜Turán類型極值問題

在前一小節(jié)，定理15的邊數換為譜半徑，結論仍然成立，那么定理15的邊數換為無符號拉普拉斯譜半徑，結論是否仍然成立？ Yuan等[31]在2014年也給出了肯定的回答.

定理20[31]令h≥1和G是一個頂點數為n≥7h2的簡單圖，則

(i) 若G不含P2h+2作為子圖,則q(G)≤q(Sn,h),等號成立當且僅當G=Sn,h；

記Mh是一個h-匹配，即Mh是由h條匹配邊組成的.易知Mh是最簡單的線性森林.Yu[32]證明了禁用(h+1)-匹配的結果，即定理21.

定理21[32]令h≥1和G是一個頂點數為n的簡單圖.若G不包含Mh+1作為子圖，則

(iii) 若n>(5h+3)/2, 則q(G)≤4h,等號成立當且僅當G=Sn,h.

(i) 若h=1且n≥8 則q(G)≤q(F2,2(n)), 并且等號成立當且僅當G=F2,2(n);

4 禁用圈的譜Turán類型極值問題

4.1 禁用圈的鄰接譜Turán類型極值問題

4.1.1 禁用奇圈

定理24中的常數n/320毫無疑問不是最優(yōu)的，但是最優(yōu)值還是個未知數.

結合定理24，易見不含奇圈作為子圖的簡單圖的緊的譜上界.

推論4[33]令h≥1且n>320(2h+1).若G是一個頂點數為n且不含C2h+1作為子圖的簡單圖，則

4.1.2 禁用C4

Nikiforov[7]在2007年給出不含C4作為子圖的簡單圖的譜半徑上界，并刻畫了極圖.

定理25[7]令G是一個頂點數為n的簡單圖，譜半徑為ρ.若G不含C4作為子圖，則ρ2-ρ-(n-1)≤0, 等號成立當且僅當G中的任意兩個頂點有且只有一個公共鄰點，也就是說G是友誼圖(G=K1∨(n-1/2)K2).

易知，使得定理25等號成立的n必然是奇數，即如果n是偶數，定理25還可以被改進.

注意到Fs,t(n)=Ks-1∨(pKt∪Kl), 其中n-s+1=pt+l, 0≤l

定理26[39]令G是一個頂點數為n的簡單圖，譜半徑為ρ.若G不含C4作為子圖，則ρ3-ρ2-(n-1)ρ+1≤0, 等號成立當且僅當G=F2,2(n).

極值圖論中很多經典結果[34]在譜極值圖論中都有相對應的譜結果，除了前面幾節(jié)介紹的，還有Matel定理在譜極值圖論對應: (定理2)若ρ(G)>ρ(T2(n)), 則G包含三角形作為子圖; Bollabás結果在譜極值圖論對應：(定理24)若ρ(G)>ρ(T2(n)), 則對每個t≤n/320,G都包含了一個長度為t的圈.

Nikiforov[42]還刻畫了定理27等號成立的條件，但是由于證明比較復雜，省去了證明.

4.1.3 禁用長度至少為6的偶圈

定理25能夠對任意的偶圈一般化為：若h≥1且G不含C2h+2作為子圖，則

實際上，Nikiforov[6]證明了更強的結果，即定理29.

定理29[6]令h≥1,1≤l≤h, 和G是一個頂點數為n的簡單圖.若G不含某個C2l+2作為子圖，則

Nikiforov[6]定義f2h+2(n):=max{ρ(G):G是一個頂點數為n且不含C2h+2作為子圖的簡單圖}.

定理29意味著

Nikiforov[6]提出了猜想3.

定理30[43]令h≥2和G是一個頂點數為n充分大的簡單圖.若G不含任意一個長度至少為2h+2的圈作為子圖，則

注意到若n≥2h+3, G不含P2h+3作為子圖，則G必不含任意一個長度至少為2h+2的圈作為子圖.定理30蘊含了定理18(ii).

4.1.4 禁用圈對{Cl,Cl+1}

Nikiforov[6]定義gl(n):=max{ρ(G):G是一個頂點數為n且不含Cl和Cl+1作為子圖的簡單圖}.

對于l≥3,gl(n)的具體值應該多少呢? Nikiforov[6]證明了漸進定理，即定理31.

定理31[6]令h≥1和G是一個頂點數為n的簡單圖.若G既不含C2h+1也不含C2h+2作為子圖，則

同時，Nikiforov[6]給出了既不含C2h+1也不含C2h+2作為子圖的簡單圖的譜極圖猜想，即猜想4.

猜想4[6]令h≥2和G是一個頂點數為n的簡單圖.若G既不含C2h+1也不含C2h+2作為子圖，則

ρ(G)≤ρ(Sn,h),

等號成立當且僅當G=Sn,h.

Yuan等[45]首先證明h=2時猜想4是正確的.最近，Gao等[43]證明了比猜想4弱的結論，即定理32.

定理32[43]令h≥2和G是一個頂點數為n≥13h2的簡單圖.若G不含任意一個長度至少為2h+1的圈作為子圖，則

ρ(G)≤ρ(Sn,h),

等號成立當且僅當G=Sn,h.

注意到若n≥2h+2,G不含P2h+2作為子圖，則G必不含任意一個長度至少為2h+1的圈作為子圖.定理32蘊含了定理18(i).

4.2 禁用圈的無符號拉普拉斯譜Turán類型極值問題

對于偶圈,q(G)和ρ(G)有類似的結果.de Freitas等[46]首先證明關于C4的相關結果.

定理33[46]令G是一個頂點數為n≥4的簡單圖.若G不含C4作為子圖，則

q(G)≤q(F2,2(n)),

等號成立當且僅當G=F2,2(n).

同時，他們也提出了關于偶圈的更一般猜想，而這猜想最后在2015年被Nikiforov等[47]解決了.

定理34[47]令h≥2和G是一個頂點數為n≥400h2的簡單圖.若G不含C2h+2作為子圖，則

對于奇圈，q(G)和ρ(G)結果是不一致的.當n充分大，不含C2h+1作為子圖的簡單圖滿足ρ(G)≤ρ(T2(n)), 但是對于q(G), de Freitas等[46]首先證明C5的相關結果.

定理35[46]令G是一個頂點數為n≥6的簡單圖.若G不含C5作為子圖，則

ρ(G)≤ρ(Sn,2),

等號成立當且僅當G=Sn,2.

同時，他們也提出了關于奇圈的更一般猜想，即猜想5.

猜想5[46]令h≥2和G是一個頂點數為n充分大的簡單圖.若G不含C2h+1作為子圖，則

q(G)≤q(Sn.h),

等號成立當且僅當G=Sn,h.

Nikiforov[48]在2014年漸進解決了猜想5.

定理36[48]令h≥2和G是一個頂點數為n>5h2的簡單圖.若q(G)≥n+2h-2,則G包含C2h+1和C2h+2作為子圖.

后來，猜想5在2015年被Yuan[49]解決了.

定理37[49]令h≥3和G是一個頂點數為n≥110h2的簡單圖.若G不含C2h+1作為子圖，則

q(G)≤q(Sn.h),

等號成立當且僅當G=Sn,h.

5 Zarankiewicz譜極值問題

在極值圖論中著名的Zarankiewicz問題[50]為：不含Ks,t作為子圖的簡單圖的最大邊數是多少？ Zarankiewicz問題的譜版本: 不含Ks,t作為子圖的簡單圖的最大譜半徑或者最大無符號拉普拉斯譜半徑是多少？除了一些特殊情況，這類問題并沒有得到完全解決.

5.1 鄰接譜的Zarankiewicz譜極值問題

Babai等[51]證明了不含Ks,t作為子圖的簡單圖的譜半徑的上界.

ρ(G)≤((s-1)1/t+o(1))n1-1/t.

Nikiforov[52]使用不同方法改進了他們的結果，即定理38.

定理38[52]令s≥t≥2和G是一個頂點數為n的簡單圖.若G不含Ks,t作為子圖，則

(ii) 若t≥3 則ρ(G)≤(s-t+1)1/tn1-1/t+(t-1)n1-2/t+t-2.

由于ρ(G)≥2e(G)/n, 定理38蘊含推論5.

推論5[52]令s≥t≥2和G是一個頂點數為n的簡單圖.若G不含Ks,t作為子圖，則

(ii) 若t≥3 則ρ(G)≤(1/2)(s-t+1)1/tn2-1/t+(1/2)(t-1)n2-2/t+(t-2)n/2.

這個結果改進了Füredi[53]的結果.

對于s=t=2, G不含K2,2作為子圖,有

定理25意味著定理38(i)的界是緊的，而且等號成立當且僅當G是友誼圖.

另外，Erd?s等[41]證明：如果q是素數冪，極性圖(polaritygraph)ERq不含K2,2作為子圖,易見ERq的頂點數為n=q2+q+1和e(ERq)=q(q+1)2/2.因此

這個界非常接近定理38(i)的上界.但是這個界并不是對所有的n都是緊的，所以它還不是最優(yōu)的.

對于s≥3, t=2, 定理38(i)是緊的，此時G可以是任意兩個頂點都有且只有s-1個公共鄰點的強正則圖.

對于s=t=3, 定理38(i)意味著：若G不含K3,3作為子圖，頂點數為n, 則

ρ(G)≤n2/3+2n1/3+1.

ρ(G)≥n2/3+(2/3)n1/3+C,

其中:C>0是某個常數.因此，定理38(ii)的界是漸進緊的.

若加入最大度參數，Shi等[55]得到了定理39.

定理39[55]令t≥2和G是一個頂點數為n的簡單連通圖.若G不含K2,t作為子圖且最大度為Δ, 則

等號成立當且僅當G是(n,Δ,t-1,t-1)-強連通圖.

5.2 無符號拉普拉斯譜的Zarankiewicz譜極值問題

不像一般的Turán類型極值問題(禁用非二部子圖)，Zarankiewicz無符號拉普拉斯譜極值問題和Zarankiewicz問題以及Zarankiewicz鄰接譜譜極值問題會有很大的差異.de Freitas等[56]提出了猜想6.

猜想6[56]令s≥t-1≥1和G是一個頂點數為n充分大的簡單圖.若G不含Kt,s+1作為子圖，則

等號成立當且僅當G=Kt-1∨H, 其中H是一個頂點數為n-t+1的簡單s正則圖.

對于特殊的s=1,t=2, 這個猜想已被證明[46].對于所有的s,t, 他們并不能證明這個猜想或給出反例.但是對于s≥1,t=2,他們證明了猜想成立.

定理40[56]令s≥1和G是一個頂點數為n≥s2+6s+6的簡單圖.若G不含K2,s+1作為子圖，則

等號成立當且僅當G=K1∨H, 其中H是一個頂點數為n-1的簡單s正則圖.

對于s+1≥t≥3， Kong等[57]給出了不含Kt,s+1作為子圖的簡單連通圖的無符號拉普拉斯譜半徑的上界，即定理41.

定理41[57]令s≥t≥3和G是一個頂點數為n≥s+t的簡單連通圖.若G不含Kt,s作為子圖，則

q(G)≤n+(s-t+1)1/tn1-1/t+(t-1)(n-1)n1-3/t+t-3.

6 禁用H-子式的譜Turán類型極值問題

當H是一個完全圖或完全二部圖，簡單圖G不含H-子式譜極值問題得到了較多的研究[58-60].

6.1 禁用Kr-子式或者Ks,t-子式

Shi等[58]給出了不含K4-子式的簡單圖的最大譜半徑，并刻畫了極圖.

定理42[58]令G是一個頂點數為n的簡單圖.若G不含K4-子式，則

Hong[59]給出了不含K5-子式的簡單圖的譜半徑上界，并刻畫了極圖.

定理43[59]令G是一個頂點數為n的簡單圖.若G不含K5-子式，則

Tait[60]把定理42、43拓展到不含Kr-子式的圖上，其中r≥3.

定理44[60]令r≥3和G是一個頂點數為n充分大的簡單圖.若G不含Kr-子式，則

下面考慮不含Ks,t-子式問題： 若s=t=2, 則簡單圖G不含K2,2-子式，且G不含K2,2作為子圖，定理26意味著ρ(G)≤ρ(F2,2(n)).由于F2,2(n)不含K2,2-子式，則等號成立當且僅當G=F2,2(n).

對于s=2,t=3, Yu等[61]給出了不含K2,3-子式的簡單圖的譜半徑上界.

定理45[61]令G是一個頂點數為n≥2的簡單圖.若G不含K2,3-子式，則

定理45的界不是緊的.類似地,Benediktovich[62]研究不含K2,4-子式的簡單2-連通圖的譜半徑上界，并給出了類似定理45的結果.

注意到Fs,t(n)=Ks-1∨(pKt∪Kl), 其中n-s+1=pt+l, 0≤l

等號成立當且僅當n≡s-1 (modt)且G=Fs,t(n).

Nikiforov[63]給出了不含K2,3-子式的簡單圖的譜半徑的緊的上界，并刻畫了極圖.

定理46[63]令G是一個頂點數為n>40 000的簡單圖.若G不含K2,3-子式，則

ρ(G)≤ρ(F2,3(n)),

等號成立當且僅當G=F2,3(n).

另外，對于t≥4, Nikiforov[63]還給出了不含K2,t-子式的簡單圖的譜半徑的緊的上界，并刻畫了極圖.

定理47[63]令t≥4和G是一個頂點數為n≥400t6的簡單圖.若G不含K2,t-子式，則

等號成立當且僅當n≡1 (modt)且G=F2,t(n).

最近，Tait[60]把定理47拓展到更一般的結果，即定理48.

定理48[60]令t≥s≥2和G是一個頂點數為n充分大的簡單圖.若G不含Ks,t-子式，則

等號成當且僅當n≡s-1 (modt)且G=Fs,t(n).

注意到如果t不能整除n-s+1, 定理48的界不是緊的.Tait[60]給出了對所有充分大的n都緊的猜想，即猜想7.

猜想7 令t≥s≥2和G是一個頂點數為n充分大的簡單圖.若G不含Ks,t-子式，則

ρ(G)≤ρ(Fs,t(n)),

等號成立當且僅當G=Fs,t(n).

6.2 可平面圖和外可平面圖

如果一個圖能同構于一個平面圖，那么稱這個圖為可平面圖.如果一個可平面圖的所有頂點都落在外面的邊界上，則這個可平面圖被稱為外可平面圖.

Wagner[64]用禁用子式給出了可平面圖的充要條件：一個圖是可平面圖當且僅當它不包含K5-子式也不包含K3,3-子式.類似地，一個圖是外可平面圖當且僅當它不包含K4-子式也不包含K2,3-子式.

可平面圖譜半徑的研究已經有很長的歷史，至少可以追溯到Schwenk等[65]的工作.Boots等[66]、Cao等[67]分別獨立提出了關于可平面圖得到最大譜半徑的極圖只有K2∨Pn-2的猜想.20多年后，這個猜想被Tait等[68]用特征向量的方法證明.

定理49[68]令G是一個頂點數為n充分大的可平面圖，則

ρ(G)≤ρ(K2∨Pn-2),

等號成立當且僅當G=K2∨Pn-2.

除此之外，Tait等[68]還用特征向量的方法證明了Cvetkovic等[69]提出的外可平面圖得到最大譜半徑的極圖的猜想，即定理50.

定理50[68]令G是一個頂點數為n充分大的外可平面圖，則

ρ(G)≤ρ(K1∨Pn-1),

等號成立當且僅當G=K1∨Pn-1.

Yu等[70]以及Yu等[71]分別用不同的方法證明了定理49、50對無符號拉普拉斯譜半徑也成立.

定理51[70]令G是一個頂點數為n≥456的可平面圖，則

q(G)≤q(K2∨Pn-2),

等號成立當且僅當G=K2∨Pn-2.

定理52[71]令G是一個頂點數為n的外可平面圖，則

q(G)≤q(K1∨Pn-1),

等號成立當且僅當G=K1∨Pn-1.

[1] BONDY J A, MURTY U S R. Graph theory[M]. New York： Springer, 2007.

[2] MANTEL W. Problem 28[J]. Wiskundige Opgaven， 1907, 10: 60-61.

[4] STANLEY R P. A bound on the spectral radius of graphs witheedges[J]. Linear Algebra Appl, 1987, 87: 267-269.

[5] WILF H S. Spectral bounds for the clique and independence numbers of graphs[J]. J Combin Theory, 1986, 40 (1): 113-117.

[6] NIKIFOROV V. The spectral radius of graphs without paths and cycles of specified length[J]. Linear Algebra Appl, 2010, 432 (9): 2243-2256.

[7] NIKIFOROV V. Bounds on graph eigenvalues II[J]. Linear Algebra Appl， 2007， 427 (2/3)： 183-189.

[8] GUIDULI B. Spectral extrema for graphs[D]. Chicago: Department of Mathematics of University of Chicago, 1998.

[9] NOSAL E. Eigenvalues of graphs[D]. Calgary: Department of Mathematics of University of Calgary, 1970.

[10] NIKIFOROV V. Some inequalities for the largest eigenvalue of a graph[J]. Combin Probab Comput, 2002, 11 (2): 179-189.

[11] NIKIFOROV V. Walks and the spectral radius of graphs[J]. Linear Algebra Appl， 2006， 418 (1)： 257-268.

[12] MOTZKIN T, STRAUS E. Maxima for graphs and a new proof of a theorem of Turán[J]. Canad J Math, 1965, 17: 533-540.

[13] EDWARDS C S, ELPHICK C H. Lower bounds for the clique and the chromatic number of a graph[J]. Discrete Appl Math, 1983, 5 (1): 51-64.

[14] NIKIFOROV V. Surveys in combinatorics[M]. London： Cambridge Univ Press, 2011: 141-181.

[15] XU M M, HONG Y,SHU J L, et al. The minimum spectral radius of graphs with a given independence number[J]. Linear Algebra Appl, 2009, 431 (5): 937-945.

[16] DU X, SHI L S. Graphs with small independence number minimizing the spectral radius[J]. Discrete Math Algorithm and Appl, 2013, 5 (3): 1350017.

[17] JIN Y L, ZHANG X D. The sharp lower bound for the spectral radins of connected graphs with the indep endence number[J]. Taiwanse Math, 2015, 19: 419-431.

[18] DE ABREU N M M, NIKIFOROV V. Maxima of theQ-index: graphs with bounded clique number[J]. Electron J Linear Algebra, 2013, 26： 121-130.

[19] HANSEN P, LUCAS C. An inequality for the signless Laplacian index of a graph using the chromatic number[J]. Graph Theory Notes N Y, 2009, 57: 39-42.

[20] HE B, JIN Y L, ZHANG X D. Sharp bounds for the signless Laplacian spectral radius in terms of clique number[J]. Linear Algebra Appl, 2013, 438 (10): 3851-3861.

[21] ERD?S P, GALLAI T. On maximal paths and circuits of graph[J]. Acta Math Acad Sci Hungar, 1959, 10 (3/4): 337-356.

[22] BALISTER P N, GY?RI E, LEHEL J, et al. Connected graphs without long paths[J]. Discrete Math, 2008, 308 (19): 4487-4494.

[23] ERD?S P. Hypergraph Seminar[M]. Berlin: Springer, 1974: 187-190.

[24] MCLENNAN A. The Erd?s-Sós conjecture for trees of diameter four[J]. J Graph Theory, 2005, 49 (4): 291-301.

[25] FAN G H，SUN L L. The Erd?s-Sós conjecture for spiders[J]. Discrete Math, 2007, 307 (23): 3055-3062.

[26] YUAN L T, ZHANG X D. On the Erd?s-Sós conjecture for graphs onn=k+4 vertices[J]. Ars Math Contemp, 2017, 13 (1): 49-61.

[27] BUSHAW N, KETTLE N. Turán numbers of multiple paths and equibipartite forests[J]. Combin Probab Comput, 2011, 20 (6): 837-853.

[29] YUAN L T, ZHANG X D. The Turán number of disjoint copies of paths[J]. Discrete Math, 2017, 340 (2): 132-139.

[30] ZHAI M Q, LIN H Q, GONG S C. Spectral conditions for the existence of specified paths and cycles in graphs[J]. Linear Algebra Appl, 2015, 471: 21-27.

[31] NIKIFOROV V, YUAN X Y. Maxima of theQ-index: graphs without long paths[J]. Electron J Linear Algebra, 2014, 27: 504-514.

[32] YU G H. On the maximal signless Laplacian spectral radius of graphs with given matching number[J]. Proc Japan Acad, 2008, 84 (8): 163-166.

[33] NIKIFOROV V. A spectral condition for odd cycles in graphs[J]. Linear Algebra Appl， 2008， 428 (7)：1492-1498.

[35] K?VARI T, SS V, TURN P. On a problem of K. Zarankiewicz[J]. Colloq Math, 1954, 3: 50-57.

[36] Reiman I. über ein problem von K. Zarankiewicz[J]. Acta Math Hungar,1958, 9 (3/4): 269-273.

[37] ERD?S P, RéNYI A, SS V T. On a problem of graph theory[J]. Stud Sci Math Hungar, 1966, 1 (4): 215-235.

[38] FüREDI Z. Graphs without quadrilaterals[J]. J Combin Theory, 1983, 34 (2): 187-190.

[39] ZHAI M Q, WANG B. Proof of a conjecture on the spectral radius ofC4-free graphs[J]. Linear Algebra Appl, 2012, 437 (7): 1641-1647.

[40] FüREDI Z. Quadrilateral-free graphs with maximum number of edges [DB/OL]. [2017-10-07]. http: //www. math. uiuc. edu/-z-furedi/PUBS/furediC4 from 1988.

[41] ERD?S P, RéNYI A. On a problem in the theory of graphs[J]. Magy Tud Akad Mat Kut Intéz K?zl, 1962, 7: 623-641.

[42] NIKIFOROV V. The maximum spectral radius ofC4-free graphs of given order and size[J]. Linear Algebra Appl, 2009, 430 (11): 2898-2905.

[43] GAO J, HOU X M. The spectral radius of graphs without long cycles[DB/OL]. [2017-11-01]. https://arxiv. org/abs/1707. 04810.

[44] FAVARON O, MAHéO M, SACLé J F. Some eigenvalue properties in graphs (conjectures of Graffiti. II)[J]. Discrete Math, 1993, 111 (1/2/3): 197-220.

[45] YUAN W L, WANG B, ZHAI M Q. On the spectral radii of graphs without given cycles[J]. Electron J Linear Algebra, 2012, 23: 599-606.

[46] DE FREITAS M A A, NIKIFOROV V, PATUZZI L. Maxima of theQ-index: forbidden 4-cycle and 5-cycle[J]. Electron J Linear Algebra, 2013 (26): 905-916.

[47] NIKIFOROV V, YUAN X Y. Maxima of theQ-index: Forbidden even cycles[J]. Linear Algebra Appl, 2015, 471 (10): 636-653.

[48] NIKIFOROV V. An asymptotically tight bound on theQ-index of graphs with forbidden cycles[J]. Publ Inst Math (Beograd) (N S), 2014, 95 (109): 189-199.

[49] YUAN X Y. Maxima of theQ-index: forbidden odd cycles[J]. Linear Algebra Appl, 2014, 458 (10): 207-216.

[50] ZARANKIEWICZ K. Problem 101[J]. Colloq Math, 1951, 2: 301.

[51] BABAI L, GUIDULI B. Spectral extrema for graphs: the Zarankiewicz problem[J]. Electron J Combin, 2009, 16 (1): R123.

[52] NIKIFOROV V. A contribution to the Zarankiewicz problem[J]. Linear Algebra Appl, 2010, 432 (6): 1405-1411.

[53] FüREDI Z. An upper bound on Zarankiewicz’s problem[J]. Comb Probab Comput, 1996, 5 (1): 29-33.

[55] SHI L S, SONG Z P. Upper bounds on the spectral radius of book-free and/orK2,l-free graphs[J]. Linear Algebra Appl, 2007, 420 (2/3): 526-529.

[56] DE FREITAS M A A, NIKIFOROV V, PATUZZI L. Maxima of theQ-index: graphs with noKs,t[J]. Linear Algebra Appl, 2016, 496: 381-391.

[57] KONG Q, WANG L. Upper bounds on theQ-spectral radius of book-free and/orKs, t-free graphs[DB/OL]. [2017-04-03]. https://arxiv. org/abs/1612. 03514.

[58] SHI J S, HONG Y. The spectral radius ofK4-minor free graph[J]. Acta Math Appl Sinica, 2001, 5: 167-175.

[59] HONG Y. Tree-width, clique-minors, andeigenvalues[J]. Discrete Math, 2004, 274 (1/2/3): 281-287.

[60] TAIT M. The Colin de Verdière parameter, excluded minors, and the spectral radius[DB/OL]. [2017-05-04]. https://arxiv. org/abs/1703. 09732.

[61] YU G L, SHU J L, HONG Y. Bounds of spectral radii ofK2,3-minor free graphs[J]. Electron J Linear Algebra, 2012, 23: 171-179.

[62] BENEDIKTOVICH V I. Spectral radius ofK2,4-minor free graph[J]. Dokl Nats Akad Nauk Belarusi, 2015, 59: 5-12 (in Russian).

[63] NIKIFOROV V. The spectral radius of graphs with noK2,t-minor[J]. Linear Algebra Appl, 2017, 531: 510-515.

[64] WAGNER K. über eine Eigenschaft der ebenen Komplexe[J]. Math Ann, 1937, 114 (1): 570-590.

[65] SCHWENK A J, WILSON R J. On the eigenvalues of a graph[J]. Selected Topics in Graph Theory, 1978, 11: 307-336.

[66] BOOTS B N, ROYLE G F. A conjecture on the maximum value of the principal eigenvalue of a planar graph[J]. Geogr Anal, 1991, 23 (3): 276-282.

[67] CAO D S, VINCE A. The spectral radius of a planar graph[J]. Linear Algebra Appl, 1993, 187 (93): 251-257.

[68] TAIT M, TOBIN J. Three conjectures in extremal spectral graph theory[J]. J Combin Theory Ser B, 2017, 126: 137-161.

[69] CVETKOVIC D, ROWLINSON P. The largest eigenvalue of a graph: a survey[J]. Linear and Multilinear Algebra, 1990, 28 (1/2): 3-33.

[70] YU G L, WANG J Y, GUO S G. Maxima of the signless Laplacian spectral radius for planar graphs[J]. Electron J Linear Algebra, 2015, 30: 795-811.

[71] YU G L, GUO S G, WU Y R. Maxima of theQ-index for outer-planar graphs[J]. Linear and Multilinear Algebra, 2015, 63 (9): 1837-1848.