The Least Eigenvalues Of The Complements Of Graphs

Spectral graph theory mainly studies the relationship between the spectral property and the structural property of graphs, discusses how the structural property of a graph is characterized by its spectral property. In 1985, Brualdi and J. Hoffman [4] presented the extreme graph problem in terms of the spec-tral radius. In the past thirty years, the extreme graph problem with respect to the spectral radius is a hot topic of spectral graph theory. However, much less is known about the least eigenvalue. As the least eigenvalue can also reflect the structure of graph, the extreme graph problem with respect to the least eigenvalue has received much attention recently.In this thesis, we discuss the least eigenvalues of the complements of graphs, characterize the structure of the minimizing graph among all the com-plements of trees, and the structure of the minimizing graph among all the complements of unicyclic graphs.The thesis is organized as follows. In Chapter one, we introduce a brief background of the spectral graph theory, the notations and concepts, the prob-lem and its development, and the results we obtained in this thesis. In Chapter two, we discuss the minimizing graph problem with respect to the least eigen-value, and determine the unique graph with the minimum eigenvalue among all the complements of trees with fixed order. In final chapter, we determine the unique graph with the minimum eigenvalue among all the complements of uicyclic graphs with fixed order.