The Investigation On The Eigenvalues Of Graphs And Mixed Graphs

The theory of graph spectra is an active and important area in graph theory. There are extensive applications in the fields of quantum chemistry, statistical mechanics, computer science and information science. In the theory of graph spectra, there are various matrices that are naturally associated with a graph, such as the adjacency matrix, the incidence matrix and the Laplacian matrix. The theory of graph spectra can be considered as an attempt to discover the properties on structures of graphs and the relations between the spectra and the invariants (e.g. chromatic number, degree sequence, girth and connectivity) of graphs by means of the well-developed theory and technique of algebra, theories of graph and combinatorics in order to establish firmly essential relation between the algebraic properties and topological properties of graphs and networks.In this paper, we study the problem about the eigenvalue of graphs and mixed graphs. Firstly, we determine the graph with the minimal least eigenvalue of the signless Laplacian among all graphs in non-bipartite unicyclic graphs with fixed pendant vertices. Secondly, we determine the graph with the minimal first eigenvalue among all graphs in nonsingular unicyclic mixed graphs with fixed pendant vertices. The main results of this thesis are as follows.In the second chapter, we study the least eigenvalue of the signless Laplacian of graphs. Let U(n, k) be the set of non-bipartite unicyclic graphs with n vertices and k pendant vertices. We determine the unique graph with the minimal least eigenvalue of the signless Laplacian among all graphs in U(n, k). Furthermore, we prove that the minimal least eigenvalue of the signless Laplacian is an increasing function on k. As an application of this result, we can directly determine the unique graph with the minimal least eigenvalue of the signless Laplacian among non-bipartite unicyclic graphs presented in the literature.In the third chapter, we study the first eigenvalue of nonsingular unicyclic mixed graphs. Let U(n, k) be the set of nonsingular unicyclic mixed graphs with n vertices and k pendant vertices. We investigate how the first eigenvalue of the Laplacian matrix of a nonsigular unicychc mixed graph changes by relocating an all-oriented tree branch from one vertex to another vertex. Using this result, we determine the unique graph with the minimal first eigenvalue of the Laplacian matrix among all graphs in u (n, k), up to a signature matrix. Furthermore, we also prove that the minimal eigenvalue of the Laplacian matrix is an increasing function on k. As an application of this result, we can directly determine the unique graph with the minimum first eigenvalue among the nonsingular unicyclic mixed graphs presented in the literature.