譜極值圖論的最新進展和相關問題

陳明珠,張曉東

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

論文系統介紹譜極值圖論的最新研究成果、進展以及相關問題.主要內容含有各種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類型極值圖論問題

譜極值圖論問題主要研究與圖相伴隨的各種矩陣，包括鄰接矩陣、拉普拉斯矩陣或無符號拉普拉斯矩陣等的譜性質，特別是關于不含有特殊……