標題: 圖的譜半徑與度數列之研究
Spectral radius and degree sequence of a graph
作者: 劉家安
Liu, Chia-An
翁志文
Weng, Chih-Wen
應用數學系所
關鍵字: 圖;二分圖;鄰接矩陣;譜半徑;度數列;graph;bipartite graph;adjacency matrix;spectral radius;degree sequence
公開日期: 2015
摘要: 令G為一n點的簡單圖,G的譜半徑\rho(G)為G之鄰接矩陣的最大特徵值。對於每個不大於n的自然數l,本論文給出一個用G圖中前l大的點度數所表示之譜半徑可達上界;此上界的應用非常廣泛,如圖的團數、無號拉普拉斯譜半徑、以及廣義r分圖。我們將此證明概念應用於二分圖譜半徑上的研究,而解決以下前人所提的猜想:給定正整數k<p<q+1,在所有從完全二分圖K_{p,q}(兩個分部分別為p點和q點)扣掉k邊後所可能產生的子圖中,擁有最大譜半徑的,為此扣掉的k邊皆和q點分部中的同一點相連。
Let G be a simple graph of order n. The spectral radius \rho(G) of G is the largest eigenvalue of its adjacency matrix. For each positive integer l at most n, this dissertation gives a sharp upper bound for \rho(G) by a function of the first l vertex degrees in G, which generalizes a series of previous results. Applications of these bounds on the clique number, signless Laplace spectral radius, and generalized r-partite graphs are provided. The idea of the above result also applies to bipartite graphs. Let k,p,q be positive integers with k<p<q+1. We prove a conjecture stating that the maximum spectral radius of a simple bipartite graph obtained from the complete bipartite graph K_{p,q} of bipartition orders p and q by deleting k edges is attained when the deleted edges are all incident on a common vertex which is located in the partite set of order q.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT079922806
http://hdl.handle.net/11536/126088
Appears in Collections:Thesis