Eigenvalues And Degree Sequences Of Graphs

The theory of graph spectral with theoretic significance andstrong application background is an important area in combinato-rial mathematics and plays an important role in quantum chemistry,computer science, communication network and information science.This thesis is devoted to discussing the first Dirichlet eigenvalue ofLaplacian matrix, which can be seen as the discrete analog of the con-tinuous Laplace-Beltrami-operator on manifolds, the eigenvalues ofweighted graphs and quasi-random bipartite graphs. First, we studythe discrete analog of Faber-Krahn inequality on manifolds. Especial-ly, we study the graphs with the minimum first Dirichlet eigenvalueamong all unicyclic graphs with a given degree sequence and with giv-en number of boundary vertices, and among the bicyclic graphs withgiven degree sequence. The results show that the Faber-Krahn typetheorem for the above graph classes holds. Second, we investigate theeigenvalues of weighted graphs. Especially, we study the p-Laplacianeigenvalues of weighted trees with a given degree sequence and a pos-itive weight set and the adjacent eigenvalues of weighted unicyclicgraphs with a given degree sequence and a positive weight set. Theresults show that the weighted tree with the largest p-Laplacian spec- tral radius among all the weighted trees with a given degree sequenceand a positive weight set is unique, which is independent of p. More-over, the weighted graphs which have the largest adjacent spectralradius among all the weighted unicyclic graphs with a given degreesequence and a positive weight set and the graphs which have thelargest adjacent spectral radius among all the unicyclic graphs witha given degree sequence have the same topological structure. At last,we study quasi-random bipartite graph and build a large equivalenceclass of bipartite graph properties. These graph properties are sharedby random bipartite graphs and reflect some essential features of ran-dom bipartite graphs.