The Spectral Characterization Of Hamiltonicity And Connectivity Of Graphs

Spectral graph theory is an important research area of algebraic graph theory. It mainly deals with spectral properties of a variety of algebraic representations of graphs, such as the Laplacian matrix, the adjacency matrix and the signless Lapla-cian matrix, and the topologicial properties of graphs by the spectral properties. It is well known that all Hamiltonian graphs must be2-vertex (edge) connected, and high connectivity of a graph implies high possibility of the graph being Hamiltonian. So there is a close relationship between hamiltonicity and connectivity of a graph. In this thesis we mainly use the spectrum to study those two related problems, i.e. hamiltonicity and connectivity of graphs.In the earlier time, almost all sufficient conditions of Hamiltonian graphs imply those graphs have too many edges, or these graphs are dense, such as the minimum degree condition by Dirac in1952, the degree sum condition by Ore in1960, the condition involved with the relation between connectivity and independence number by Chvatal and Erdos in1972. However, when a graph has more vertices or edges, it is difficult to determine whether the graph is Hamiltonian or not by directly using those or similar conditions. In2010Fiedler and Nikiforov gave some sufficient con-ditions of Hamiltonian graphs by using the spectral radius of the adjacency matrix. Laterly Zhou characterized hamiltonicity of a graph by the spectral radius of the signless Laplace matrix. These spectral conditions are a little more feasible because the spectrum is easy to calculate. Motivatied by the above work, we further study the relationship between the eigenvalues of a variety of matrices and hamiltonicity of graphs, and give some sufficient conditions for a graph to be Hamiltonian. We also apply this method to characterize higher connectivity of a graph, such as the Hamilton-connected graphs.In fact, there exist a large number of sparse Hamiltonian graph, such as cycles However the research on this topic receives less attention. The breakthrough is that Komlos and Szemeredi gave a surprisingly result in1975that almost surely a random graph is Hamiltonian. In2003Krivelevich and Sudakov gave a sufficient condition of a regular graph to be Hamiltionian by the spectrum of the adjacency matrix, where the graphs satisfying the given condition are pseudo-random. They conjectured this method can be applied to almost regular graphs. In2010Butler and Chung confirmed the conjecture, and gave a sufficient condition of almost regular graphs to be Hamiltonian by using the Laplacian spectrum of a graph. In2011Radcliffe posed the problem whether one can find sufficient conditions by the spectrum (or spectral gap) of the normalized Laplacian to ensure that a graph is Hamiltonian. We focus on this proplem and give a sufficient condition of a graph to be Hamiltonian by the normalized Laplace spectrum. In the case of regular graphs, our result implies the results of the above two work.As mentioned before, the discussion of connectivity of a graph is very important and useful to the Hamiltonicity of the graph. There is a good characterization of the structure of graphs whose vertex (edge)-connectivity is2or3. On the characterization of the connectivity of a graph from the algebraic view, the most classical concept is the algebraic connectivity of a graph, i.e. the second smallest eigenvalue of the Laplacian of the graph, which is introduced by Fiedler in1972. There are also some characterizations of the connectivity of a graph by using the spectral radius of the adjacency matrix. However the relationship between the least eigenvalue of the adjacency matrix and the connectivity of a graph receives less attention. In1985Constantine determined the graph with minimum least eigenvalue among all graphs with fixed order, which is a complete bipartite graph with almost equal bipartition. But the complement, of this graph is disconnected. So we study the least eigenvalue of the class of graphs with fixed order whose complements are connected, and characterize the unique graph with minimum least, eigenvalue among all graphs in this class. We also discuss the least eigenvalue of a graph whose complement has no cut vertices or cut edges, namely whose complement is2-vertex (edge) connected, and characterize the unique graph with minimum least eigenvalue among all graphs in such class.Finally we study the relationship between the connectivity and the least signless Laplacian eigenvalue of a graph. In2008Cardoso et al. determined the unique graph with minimum least singless Laplacian eigeenvalue among all non-bipartite graphs of fixed order, whose vertex or edge connectivity is very small. We guess among a certain class of non-bipartite graphs, the graphs with minimum least singless Laplacian eigenvalue should have a very small connectivity. We verify this idea on non-bipartite bicyclic graphs. We find that the extremal graph is a balance between the small connectivity and large bipartiteness, that is, it has a large number of cut vertices or cut edges and a large number of even cycles.