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

Spectral radius and degree sequence of a graph

劉家安(Chia-An Liu)

指導教授 ： 翁志文

國立交通大學/理學院/應用數學系暨研究所/博士(2015年)

https://doi.org/10.6842/NCTU.2015.00248

摘要

令G為一n點的簡單圖，G的譜半徑
ho(G)為G之鄰接矩陣的最大特徵值。對於每個不大於n的自然數l，本論文給出一個用G圖中前l大的點度數所表示之譜半徑可達上界；此上界的應用非常廣泛，如圖的團數、無號拉普拉斯譜半徑、以及廣義r分圖。我們將此證明概念應用於二分圖譜半徑上的研究，而解決以下前人所提的猜想：給定正整數k

關鍵字

圖 ； 二分圖 ； 鄰接矩陣 ； 譜半徑 ； 度數列

並列摘要

Let G be a simple graph of order n. The spectral radius
ho(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
ho(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

並列關鍵字

graph ； bipartite graph ； adjacency matrix ； spectral radius ； degree sequence

參考文獻

[1] F.K. Bell, On the maximal index of connected graphs, Linear Algebra Appl. 144 (1991) 135-151.

[2] A. Berman and X.-D. Zhang, On the spectral radius of graphs with cut vertices, J. Combin. Theory Ser. B 83 (2001) 233-240.

[6] A. Bojilov, Y. Caro, A. Hansberg and N. Nenov, Partitions of graphs into small and large sets, Discrete Appl. Math. 161 (2013) 1912-1924.

[7] A.E. Brouwer, A.M. Cohen and A. Neumaier, Distance-Regular Graphs, Springer-Verlag, Berlin, 1989.

[9] R.A. Brualdi and A.J. Hoffman, On the spectral radius of (0; 1)-matrices, Linear Algebra Appl. 65 (1985) 133-146.