The Spectral Extremal Theory Of Graphs

The spectral extremal theory of graphs is a cross field of study-ing extremal graph theory and algebraic graph theory. It is a main researching direction and focus of graph theory emerging recently, which is widely applied in the field of computer science and engineer-ing. The thesis contains three parts:● Firstly, in chapter 2, we study the structure properties of complete subgraphs of graphs with the number of maximal cliques and the number of vertices and characterize the extremal graph with max-imum number of cliques in this graph class, which extends and enhances Turan theorem, Moon theorem and Hedman theorem. Moreover, we also prove the famous spectral Turan theorem which was proved independently by Guiduli and Nikiforov. In chapter 3, we study another form of the spectral Turan’s theorem, i.e. the minimum spectral radius given independence number.● Secondly, we study the spectral extremal theory incident with chemistry graph theory. In the chapter 4, we consider the Lapla-cian coefficients of trees with maximum degree. Build the relation between the Laplacian coefficients and the matching polynomial- s of graphs, and characterize the extremal trees with minimum matching polynomials and characterize the extremal trees with the minimum incidence energy. In chapter 5,6, we study the relation between the polynomial of distance matrix and Weiner index. Using the theory of algebra and graphs to prove two con-jectures proposed by Sills and Wang, Lin Huiqiu, Hong Yuan, Wang Jianfeng and Shu Jinlong, respectively.● In the end, in chapter 7, we study the maximum spectral radius of simple digraphs given arc number. Using the skill of matrix norm gives the sharp upper bound of the spectral radius of sim-ple digraphs, and characterize the extremal simple digraphs with maximum spectral radius.