On The Relationships Between The Edge-disjoint Spanning Trees And Eigenvalues In Regular Graphs

Graph theory is an important branch of combinatorics, a powerful tool to deal with discrete mathematics problems and an active and important subject with long history. The study of graph spectra theory has been a hot issue in graph theory.There are various matrices that are naturally associated with a graph, such as the adjacency matrix, the distance matrix, the Laplacian matrix, the signless Laplacian matrix and so on. One of the main problems of graph spectra theory is to study the eigenvalues of these matrix and the relationships between various invariants of a graph and their eigenvalues.Motivated by a question of Seymour on the relationships between eigenvalues of a graph and bounds of the maximum number of edge-disjoint spanning trees, Cioaba and Wong conjec-tured that for any integers d,k≥2and a d-regular graph G, ifλ2(G)<d-2k-1/d+1, then τ(G)≥k. They proved the conjecture for k=2,3. The main work of this paper is to continue to study the relationships between eigenvalues of a simple connected graph G and bounds of τ(G),(i) In Chapter1, we first introduce the history of graph theory and the backgrounds of some questions on graph spectra theory that we study. Then, some definitions and notations for the corresponding questions are introduced.(ii) In Chapter2, we summarize some recent studying of the bound on the second largest eigenvalue of difference kinds of graphs.(iii) In Chapter3, according to Cioaba and Wong’s conjecture, we further verify the con-jecture for the case when k=4. Moreover, we improve the existing partial results towards the conjecture for other values of k. Lastly, we construct examples of graphs that show our bounds are essentially best possible.