Some Problems In Algebraic Graph Theory

Algebraic graph theory is an important branch of graph theory in which methods and results of algebra are applied to problems about graphs. The spectral graph theory is one of the main topics in algebraic graph theory. To study properties of graphs, its principal method is to use matrix theory to research the algebraic properties of these matrice. Since some graph invariants are contained in some graph polynomials, people usually use theory of polynomials to study properties of graphs. Thus, the theory of graph polynomials is another main branch in algebraic graph theory. Both the spectral graph theory and theory of graph polynomials have some importances in theories and applications. Concerning the two topics, the thesis mainly considers two kinds of problems. One is the extremal problems on the spectrum and topological indexes concerning the spectrum in a given set of graphs, and the other is the unimodality problems of independence polynomials of graphs. The main results can be summarized as follows:The first part of the thesis mainly studies the extremal problems on the signless Laplacian spectral radius of all the connected graphs (respectively, bipartite graphs) with n vertices and k cut vertices, and respectively obtains the upper bounds of the signless Laplacian spectral radius and describes the corresponding extremal graphs. Similarly, the author may give a new proof of the analogous result of Berman and Zhang for the spectral radius and extend the result of Fan and Wang for the least eigenvalue of all the connected graphs with n vertices and k cut vertices.The second part considers the extremal problems on the least eigenvalue of all the connected graphs with n vertices and k cut edgs (respectively, maximum degree△). The author presents the lower bounds on the least eigenvalue in terms of n and k (respectively,△), and characterizes the corresponding extremal graphs.The third part researches the extremal problems on the Laplacian-energy like and Laplacian Estrada index of all the connected graphs with n vertices and connectivity k (respectively, chromatic numberχand matching numberβ). The author obtains the upper bounds on the Laplacian-energy like and Laplacian Estrada index in terms of n and k (respectively,χandβ), and determines the corresponding extremal graphs.The fourth part gives factorizations of independence polynomials for certain classes of graphs. As applications, on one hand the independence polynomials of vertebrated graphs and firecracker graphs are showed to be log-concave and unimodal. This demonstrates the results of Levit, Mandrescu and Zhu Zhifeng in a unified manner, particularly confirms a conjecture of Zhu Zhifeng and futher negatives a conjecture of Levit and Mandrescuon on the modal of independence polynomials of centipede graphs. On the other hand, the author also extends the Chudnovsky and Seymour's result. Similarly, the author confirms Levit and Mandrescu's an unimodaliy conjecture. Finally, the method also adapts to other graph polynomials.