譜極值圖論的最新進(jìn)展和相關(guān)問(wèn)題

陳明珠,張曉東

(上海交通大學(xué) 數(shù)學(xué)科學(xué)學(xué)院,教育部科學(xué)工程計(jì)算重點(diǎn)實(shí)驗(yàn)室,上海 200240)

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

Turán類型問(wèn)題；禁用子圖；譜半徑；無(wú)符號(hào)拉普拉斯譜半徑

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

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

1 Turán類型極值圖論問(wèn)題

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

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

2 譜Turán定理

2.1 鄰接譜Turán定理

Wilf[5]在1986年利用圖的頂點(diǎn)數(shù)和團(tuán)數(shù)，給出了圖的譜半徑的上界.

定理1[5]令G是一個(gè)頂點(diǎn)數(shù)為n的簡(jiǎn)單圖.若G的團(tuán)數(shù)為ω(G)=ω, 則

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

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

定理2 令G是一個(gè)頂點(diǎn)數(shù)為n的簡(jiǎn)單圖.若G不含Kr+1作為子圖，則

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

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

定理3[7-8]令G是一個(gè)頂點(diǎn)數(shù)為n的簡(jiǎn)單圖.若G不含Kr+1作為子圖，則

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

等號(hào)成立當(dāng)且僅當(dāng)G=Tn,r.

實(shí)際上，定理3也改進(jìn)了定理1，它等價(jià)于定理4.

定理4 令G是一個(gè)頂點(diǎn)數(shù)為n的簡(jiǎn)單圖.若G的團(tuán)數(shù)為ω(G)=ω, 則

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

等號(hào)成立當(dāng)且僅當(dāng)G=Tn,ω.

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

推論1[3]令G是一個(gè)頂點(diǎn)數(shù)為n的簡(jiǎn)單圖.若G不含Kr+1作為子圖，則

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

等號(hào)成立當(dāng)且僅當(dāng)G=Tn,r.

若G沒(méi)有孤立點(diǎn),則等號(hào)成立當(dāng)且僅當(dāng)下列兩種情況之一成立：

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

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

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

推論2[10]令G是一個(gè)頂點(diǎn)數(shù)為n的簡(jiǎn)單圖.若G的團(tuán)數(shù)為ω(G)=ω, 則

若G沒(méi)有孤立點(diǎn),則等號(hào)成立當(dāng)且僅當(dāng)下列兩種情況之一成立：

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

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

定理6[11]令G是一個(gè)頂點(diǎn)數(shù)為n的簡(jiǎn)單圖.若G的團(tuán)數(shù)為ω(G)=ω, 則

若G沒(méi)有孤立點(diǎn),k≥1, 則等號(hào)成立，則

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

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

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

2.2 譜半徑和獨(dú)立數(shù)

ρ(G)≥n/α-1.

實(shí)際上，譜半徑和獨(dú)立數(shù)滿足下列更精確的結(jié)果如下：

定理7[14]令G是一個(gè)頂點(diǎn)數(shù)為n的簡(jiǎn)單圖.若G的獨(dú)立數(shù)為α, 則

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

定理8[16]令G是一個(gè)獨(dú)立數(shù)為α的頂點(diǎn)數(shù)為n=kα的簡(jiǎn)單連通圖.若α=3,4, 則

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

其中：圖Pn,α是把一條長(zhǎng)為α-1的路中每個(gè)頂點(diǎn)被k的團(tuán)取代并且有2α-2個(gè)割點(diǎn)所得到的簡(jiǎn)單圖.

最近Jin等[17]進(jìn)一步考慮一般情形，并且推廣他們的結(jié)果.

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

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

其中：圖Pn,α是把一條長(zhǎng)為α-1的路中每個(gè)頂點(diǎn)被k的團(tuán)取代并且有2α-2個(gè)割點(diǎn)所得到的簡(jiǎn)單圖，等號(hào)成立當(dāng)且僅當(dāng)G是Pn,α.

顯然上面定理并沒(méi)有完全刻畫獨(dú)立數(shù)為α的n個(gè)頂點(diǎn)的簡(jiǎn)單連通圖中具有最小譜半徑的所有極圖，這是一個(gè)非常有趣的問(wèn)題.

2.3 無(wú)符號(hào)拉普拉斯譜Turán定理

Abreu等[18]在2013年研究給定頂點(diǎn)數(shù)和團(tuán)數(shù)的簡(jiǎn)單圖的無(wú)符號(hào)拉普拉斯譜半徑，證明了Hansen等[19]在2009年提出的猜想.

定理10[18]令G是一個(gè)頂點(diǎn)數(shù)為n的簡(jiǎn)單圖.若G的團(tuán)數(shù)為ω(G)=ω, 則

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

類似于定理1等價(jià)于定理2，定理10也等價(jià)于以下定理：

定理11 令G是一個(gè)頂點(diǎn)數(shù)為n的簡(jiǎn)單圖.若G不含Kr+1作為子圖，則

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

He等[20]在2013年也研究給定頂點(diǎn)數(shù)和團(tuán)數(shù)的簡(jiǎn)單圖，給出了這類圖的無(wú)符號(hào)拉普拉斯譜半徑的緊的上界，并刻畫了極圖.

定理12[20]令G是一個(gè)頂點(diǎn)數(shù)為n的簡(jiǎn)單圖.若G的團(tuán)數(shù)為ω(G)=ω≥2, 則

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

另外，等號(hào)成立當(dāng)且僅當(dāng)下面情況之一成立：

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

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

定理12等價(jià)于定理13.

定理13[20]令r≥2和G是一個(gè)頂點(diǎn)數(shù)為n的簡(jiǎn)單圖.若G不含Kr+1作為子圖，則

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

另外，等號(hào)成立當(dāng)且僅當(dāng)下面情況之一成立：

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

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

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

推論3[3]令r≥3和G是一個(gè)頂點(diǎn)數(shù)為n的簡(jiǎn)單圖.若G不含Kr+1作為子圖，則

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

等號(hào)成立當(dāng)且僅當(dāng)G=Tn,r.

若r≥3, 定理3、13的極圖是一致的.但是當(dāng)r=2, 定理3的極圖是唯一的，而定理13的極圖卻不是唯一的.這是因?yàn)橥耆繄D的無(wú)符號(hào)拉普拉斯譜半徑就是它的頂點(diǎn)數(shù).這說(shuō)明鄰接譜極圖和無(wú)符號(hào)拉普拉斯譜極圖并不定是完全一致的.

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

Erd?s等[21]在1959年給出了不含給定長(zhǎng)度的路作為子圖的簡(jiǎn)單圖的最大邊數(shù).

定理14[21]令h≥2和G是一個(gè)頂點(diǎn)數(shù)為n的簡(jiǎn)單圖.若G不含Ph作為子圖，則

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

等號(hào)成立當(dāng)且僅當(dāng)G是頂點(diǎn)數(shù)為h-1的完全圖的不交并.

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

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

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

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

猜想1[23]令h≥2.如果簡(jiǎn)單圖G的平均度超過(guò)h-2, 則G包含所有頂點(diǎn)數(shù)為h的樹作為子圖.

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

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

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

關(guān)于F=lP3, Yuan等[29]刻畫了對(duì)應(yīng)所有極圖.

定理17[29]令F=lP3和G是一個(gè)頂點(diǎn)數(shù)為n的簡(jiǎn)單圖.若G不含F(xiàn)作為子圖，則

(i) 當(dāng)n<3k時(shí)，e(G)≤n(n-1)/2;

并且刻畫了所有的極圖.

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

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

定理18[6]令h≥1和G是一個(gè)頂點(diǎn)數(shù)為n≥24h的簡(jiǎn)單圖,則

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

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

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

猜想2[6]令h≥2和G是一個(gè)頂點(diǎn)數(shù)為n充分大的簡(jiǎn)單圖，則

(1) 若G不含某頂點(diǎn)數(shù)為2h+2的樹作為子圖，則ρ(G)≤ρ(Sn,h),等號(hào)成立當(dāng)且僅當(dāng)G=Sn,h；

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

回到線性森林的問(wèn)題上，指出定理16對(duì)應(yīng)的譜半徑版本也成立，而它的證明幾乎可以把定理18的證明移植過(guò)來(lái).

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

3.2 禁用線性森林的無(wú)符號(hào)拉普拉斯譜Turán類型極值問(wèn)題

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

定理20[31]令h≥1和G是一個(gè)頂點(diǎn)數(shù)為n≥7h2的簡(jiǎn)單圖，則

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

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

定理21[32]令h≥1和G是一個(gè)頂點(diǎn)數(shù)為n的簡(jiǎn)單圖.若G不包含Mh+1作為子圖，則

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

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

4 禁用圈的譜Turán類型極值問(wèn)題

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

4.1.1 禁用奇圈

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

結(jié)合定理24，易見(jiàn)不含奇圈作為子圖的簡(jiǎn)單圖的緊的譜上界.

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

4.1.2 禁用C4

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

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

易知，使得定理25等號(hào)成立的n必然是奇數(shù)，即如果n是偶數(shù)，定理25還可以被改進(jìn).

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

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

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

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

4.1.3 禁用長(zhǎng)度至少為6的偶圈

定理25能夠?qū)θ我獾呐既σ话慊癁椋喝鬶≥1且G不含C2h+2作為子圖，則

實(shí)際上，Nikiforov[6]證明了更強(qiáng)的結(jié)果，即定理29.

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

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

定理29意味著

Nikiforov[6]提出了猜想3.

定理30[43]令h≥2和G是一個(gè)頂點(diǎn)數(shù)為n充分大的簡(jiǎn)單圖.若G不含任意一個(gè)長(zhǎng)度至少為2h+2的圈作為子圖，則

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

4.1.4 禁用圈對(duì){Cl,Cl+1}

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

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

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

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

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

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

等號(hào)成立當(dāng)且僅當(dāng)G=Sn,h.

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

定理32[43]令h≥2和G是一個(gè)頂點(diǎn)數(shù)為n≥13h2的簡(jiǎn)單圖.若G不含任意一個(gè)長(zhǎng)度至少為2h+1的圈作為子圖，則

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

等號(hào)成立當(dāng)且僅當(dāng)G=Sn,h.

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

4.2 禁用圈的無(wú)符號(hào)拉普拉斯譜Turán類型極值問(wèn)題

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

定理33[46]令G是一個(gè)頂點(diǎn)數(shù)為n≥4的簡(jiǎn)單圖.若G不含C4作為子圖，則

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

等號(hào)成立當(dāng)且僅當(dāng)G=F2,2(n).

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

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

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

定理35[46]令G是一個(gè)頂點(diǎn)數(shù)為n≥6的簡(jiǎn)單圖.若G不含C5作為子圖，則

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

等號(hào)成立當(dāng)且僅當(dāng)G=Sn,2.

同時(shí)，他們也提出了關(guān)于奇圈的更一般猜想，即猜想5.

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

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

等號(hào)成立當(dāng)且僅當(dāng)G=Sn,h.

Nikiforov[48]在2014年漸進(jìn)解決了猜想5.

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

后來(lái)，猜想5在2015年被Yuan[49]解決了.

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

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

等號(hào)成立當(dāng)且僅當(dāng)G=Sn,h.

5 Zarankiewicz譜極值問(wèn)題

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

5.1 鄰接譜的Zarankiewicz譜極值問(wèn)題

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

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

Nikiforov[52]使用不同方法改進(jìn)了他們的結(jié)果，即定理38.

定理38[52]令s≥t≥2和G是一個(gè)頂點(diǎn)數(shù)為n的簡(jiǎ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蘊(yùn)含推論5.

推論5[52]令s≥t≥2和G是一個(gè)頂點(diǎn)數(shù)為n的簡(jiǎ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.

這個(gè)結(jié)果改進(jìn)了Füredi[53]的結(jié)果.

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

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

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

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

對(duì)于s≥3, t=2, 定理38(i)是緊的，此時(shí)G可以是任意兩個(gè)頂點(diǎn)都有且只有s-1個(gè)公共鄰點(diǎn)的強(qiáng)正則圖.

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

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

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

其中:C>0是某個(gè)常數(shù).因此，定理38(ii)的界是漸進(jìn)緊的.

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

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

等號(hào)成立當(dāng)且僅當(dāng)G是(n,Δ,t-1,t-1)-強(qiáng)連通圖.

5.2 無(wú)符號(hào)拉普拉斯譜的Zarankiewicz譜極值問(wèn)題

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

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

等號(hào)成立當(dāng)且僅當(dāng)G=Kt-1∨H, 其中H是一個(gè)頂點(diǎn)數(shù)為n-t+1的簡(jiǎn)單s正則圖.

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

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

等號(hào)成立當(dāng)且僅當(dāng)G=K1∨H, 其中H是一個(gè)頂點(diǎn)數(shù)為n-1的簡(jiǎn)單s正則圖.

對(duì)于s+1≥t≥3， Kong等[57]給出了不含Kt,s+1作為子圖的簡(jiǎn)單連通圖的無(wú)符號(hào)拉普拉斯譜半徑的上界，即定理41.

定理41[57]令s≥t≥3和G是一個(gè)頂點(diǎn)數(shù)為n≥s+t的簡(jiǎn)單連通圖.若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類型極值問(wèn)題

當(dāng)H是一個(gè)完全圖或完全二部圖，簡(jiǎn)單圖G不含H-子式譜極值問(wèn)題得到了較多的研究[58-60].

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

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

定理42[58]令G是一個(gè)頂點(diǎn)數(shù)為n的簡(jiǎn)單圖.若G不含K4-子式，則

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

定理43[59]令G是一個(gè)頂點(diǎn)數(shù)為n的簡(jiǎn)單圖.若G不含K5-子式，則

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

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

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

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

定理45[61]令G是一個(gè)頂點(diǎn)數(shù)為n≥2的簡(jiǎn)單圖.若G不含K2,3-子式，則

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

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

等號(hào)成立當(dāng)且僅當(dāng)n≡s-1 (modt)且G=Fs,t(n).

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

定理46[63]令G是一個(gè)頂點(diǎn)數(shù)為n>40 000的簡(jiǎn)單圖.若G不含K2,3-子式，則

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

等號(hào)成立當(dāng)且僅當(dāng)G=F2,3(n).

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

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

等號(hào)成立當(dāng)且僅當(dāng)n≡1 (modt)且G=F2,t(n).

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

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

等號(hào)成當(dāng)且僅當(dāng)n≡s-1 (modt)且G=Fs,t(n).

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

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

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

等號(hào)成立當(dāng)且僅當(dāng)G=Fs,t(n).

6.2 可平面圖和外可平面圖

如果一個(gè)圖能同構(gòu)于一個(gè)平面圖，那么稱這個(gè)圖為可平面圖.如果一個(gè)可平面圖的所有頂點(diǎn)都落在外面的邊界上，則這個(gè)可平面圖被稱為外可平面圖.

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

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

定理49[68]令G是一個(gè)頂點(diǎn)數(shù)為n充分大的可平面圖，則

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

等號(hào)成立當(dāng)且僅當(dāng)G=K2∨Pn-2.

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

定理50[68]令G是一個(gè)頂點(diǎn)數(shù)為n充分大的外可平面圖，則

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

等號(hào)成立當(dāng)且僅當(dāng)G=K1∨Pn-1.

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

定理51[70]令G是一個(gè)頂點(diǎn)數(shù)為n≥456的可平面圖，則

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

等號(hào)成立當(dāng)且僅當(dāng)G=K2∨Pn-2.

定理52[71]令G是一個(gè)頂點(diǎn)數(shù)為n的外可平面圖，則

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

等號(hào)成立當(dāng)且僅當(dāng)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.