The Least Eigenvalues Of Graphs

Spectral graph theory is an important research field of graph theory and combinatorial matrix theory, mainly studies the relationship between the spec-tral property and the structural property of graphs, discusses how the struc-tural property of a graph is characterized by its spectral property.In past years, studying extreme spectral parameters and extremal spectral property of graphs have been the research focuses of spectral graph theory. In general, extreme spectral parameters involve spectral radius, least eigenvalue, second largest eigenvalue, second least eigenvalue and their combinations, etc. As we all known, extreme spectral parameters usually imply more structural information than other eigenvalues, so they have received much attention. Ex-tremal spectral property of a graph refers to the property of some spectral parameter of a graph while it satisfies some extremal(maximal, minimal, crit-ical, etc) conditions. The familiar problem of extremal spectral property is the extreme graph problem, that is, determining the graph whose some eigen-value attains maximum(minimum) among a certain class of graphs subject to one or more given parameters. Researchers attempt to study the the relation-ship between the spectral property and the structural property of graphs by discussing the structure of extreme graph.In the past thirty years, the extreme graph problem with respect to the spectral radius is a hot topic of spectral graph theory. The least eigenvalue, the other extreme eigenvalue, also reflects the structural property of a graph well, is also on interest. As we all known, the least nontrivial eigenvalue in terms of Laplacian matrix of a graph, is called algebraic connectivity[37], is important to characterize the connectivity of a graph. There are many results in literatures concerning the algebraic connectivity of a graph. However, much less is known about the least eigenvalue in terms of adjacency matrix and signless Laplacian matrix. In fact, they are also two powerful tool to characterize the structure of graphs. For example, the least eigenvalue in terms of adjacency matrix can help to decide whether a graph can be as the line graph of some graph [21], the least Q-eigenvalue can be considered as the measure of bipartiteness of a graph[31,32]. In this thesis, we discuss the extremal spectral property with respect to the least eigenvalue and the least Q-eigenvalue, and study the relationship between them and the structural property of graphs.In Chapter1, we firstly introduce a background of the spectral theory of graphs, some concepts and notations used in this thesis, then discuss the research problems, their developments together with the main results we obtain in this thesis.In Chapter2, we discuss the relationship between the least eigenvalue and two structural parameters (number of cut vertices and number of cut edges), characterize the minimizing graph among all connected graphs given the num-ber of cut vertices and the number of cut edges, respectively. In addition, we also characterize the maximizing graph among all connected bipartite graphs given the number of cut vertices and given the number of cut edges, respec-tively.In Chapter3, we discuss the least eigenvalue of complement of graphs, attempt to study the structure of a graph by the least eigenvalue of complement of a graph, characterize the minimizing graph among all the complements of trees, and the minimizing graph among all the complements of unicyclic graphs.In final Chapter, we discuss the least Q-eigenvalue of graphs. In section4.1, we give a few of combinatorial properties of the first Q-cigcnvector of a graph, investigate how the least Q-eigenvalue of a graph changes under some structural perturbation. Using these results, in section4.2, we minimize the least Q-eigenvalue among all connected graphs with fixed order which con-tains a given non-bipartite graph as an induced subgraph. In section4.3, we determine the unique graph with minimum least Q-eigenvalue, and the graph with maximum least Q-eigenvalue among all graphs of order n with k pendant vertices, respectively.