圖的譜半徑與度數列之研究

Abstract

令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.