Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Graphs with Given Degree Sequence and Maximal Spectral Radius. | Graphs with Given Degree Sequence and Maximal Spectral Radius Turker Biyikoglu Department of Mathematics I ik University Sile 34980 Istanbul Turkey Josef Leydold Department of Statistics and Mathematics University of Economics and Business Administration Augasse 2-6 A-1090 Wien Austria Submitted Jul 6 2007 Accepted Sep 7 2008 Published Sep 15 2008 Mathematics Subject Classification 05C35 05C75 05C05 Abstract We describe the structure of those graphs that have largest spectral radius in the class of all connected graphs with a given degree sequence. We show that in such a graph the degree sequence is non-increasing with respect to an ordering of the vertices induced by breadth-first search. For trees the resulting structure is uniquely determined up to isomorphism. We also show that the largest spectral radius in such classes of trees is strictly monotone with respect to majorization. Keywords adjacency matrix eigenvectors spectral radius degree sequence Perron vector tree majorization 1 Introduction Let G V E be a simple finite undirected graph with vertex set V G and edge set E G . The eigenvalue of G are the eigenvalues of the adjacency matrix A G . The spectral radius of G is the largest eigenvalue of A G also called the index of the graph. When G is connected A G is irreducible and by the Perron-Frobenius Theorem see . 8 the largest eigenvalue A G of G is simple and there is a unique positive unit eigenvector. We refer to such an eigenvector f as the Perron vector of G. There exists a vast literature that provides upper and lower bounds on the largest eigenvalue of G given some information about the graph for previous results see 5 . THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R119 1 Many recent results use the maximum minimum or average degrees . 10 13 . Some new results are based on the entire degree sequence . 15 . The goal of this article is slightly shifted. We want to characterize .
