Some Results On Spectra Of Graphs And Sign Patterns

On the last two decades or so work in combinatorics and graph theory with matrix and linear algebra techniques, and applications of graph theory and combinatorics to linear algebra have developed rapidly. The theory of graph spectra and the study about sign pattern matrices are the important components of combinatorial matrix theory. The theory of graph spectra is an active and important area in graph theory. There are extensive appli-cations in the fields of quantum chemistry, statistical mechanics, computer science, communication networks 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, the Laplacian matrix, the signless Laplacian matrix, the distance matrix and so on. One of the main problems of graph spectra theory is to determine precisely how, or whether, properties of graphs are reflected in the algebraic properties (such as spectral radius, spectral uniqueness, spread, energy and so on) of such matrices. The study about sign pattern matrices is of great significance in the fields of economics, biology, chemistry, sociology, communication, theo-retical computer science and so on. The study about sign pattern matrices involves the property of the power sequence of a sign pattern matrix, solv-ability, stability and so on. The study about sign pattern matrices in this thesis involves mainly the property of the power sequence of a sign pattern matrix.On theory of graph spectra, we mainly investigates the spectral radii, eigenvalues, the least eigenvalues and the spreads for adjacency matrices, signless Laplacian matrices (Q-matrix) and distance matrices of graphs and tries to build some connections between them and some structure variables of corresponding graphs. On the property of the power sequence of a sign pattern matrix, the extremal primitive digraphs with both Lewin index n-2 and girth 2 or 3 are determined, and both the base set and extremal digraph with the maximal base for some special classes of sign pattern matrices are well determined. After the work of professors J. Shao, B. Liu, L. You and Z. Miao, and after some work in my master graduation thesis, some new bounds about primitive nonpowerful sign pattern matrices are given and some new gaps in the base set are shown. The main content of this thesis are as follows.(1) In Chapter 1, we first look back the evolvement of graph theory. Secondly, we introduce the backgrounds and research progresses of some questions on graph spectra theory that we study. Finally, we introduce the backgrounds and research progresses of the study work about sign pattern matrices.(2) In Chapter 2, we investigate the A-spectra (adjacency spectra) of graphs with order n. In the first section, some basic definitions, notations and working lemmas are introduced. In section 2 and 3, we first investigate the connections between the minor and the spectra of a graph and investigate the connections between the topological properties and the algebraic properties. For K2,3-minor free graphs and edge most outer-planar graphs, we give some structural characterization, and give some bounds on their spectral radii. At the end of this chapter, we investigate the least eigenvalue of an bicyclic graph with given diameter in order to give a sharp lower bound on the least eigenvalue and characterize the extremal graph with the least eigenvalue.(3) In Chapter 3, we investigate the Q-spectra (signless Laplacian spec-tral) of graphs with order n. In the fist section, some basic definitions, notations and working lemmas are introduced. In the second section, we give some bounds on the Q-spectral radius of a general graph and charac-terize the extremal graph with the maximal Q-spectral radius. In sections 3,4, for the graphs with both given order and the chromatic number, we determine the extremal graphs with the maximal Q-spectral radius and the minimal Q-spectral radius respectively. In the last section, the graphs with q2(G)= 2 are determined; for the simple connected non-bipartite graphs with n≥9 vertices, the graphs with q2(G)≤3 are determined; and for the simple connected bipartite graphs with n≥7 vertices, the graphs with q2(G)≤3 are determined. We show that (i) if n≥2, there is no connected graph G with order n such that q2(G)∈((1,2)∪(3+(?)/2,2.7)); (ii) if n≥9, there is no connected graph G with order n such that q2(G)∈((1,3+(?)/2)∪(3+(?)/2,2.7)), and we determine that 3 is the least Q-limit point of q2(4) In Chapter 4, we investigate the distance spectra of graphs with order n. In the fist section, some graft transformations that decrease or increase g(G) are given. With them, for the graphs with both order n and k pedant vertices, the extremal graph with the minimum distance spectral radius is shown to be a graph H obtained by attaching k pendant edges to a vertex of a n-k vertices complete graph, and the extremal graph with the maximum distance spectral radius is shown to be a dumbbell graph. In the second section, we also give some graft transformations that decrease or increase g(G). With them, we proved that the graph Sn' (obtained from the star Sn on n vertices by adding an edge connecting two pendent vertices) has minimal distance spectral radius among unicyclic graphs on n vertices; while Pn' (obtained from a triangle K3 by attaching pendent path Pn₃ to one of its vertices) has maximal distance spectral radius among unicyclic graphs on n vertices. Finaly, for simple connected graphs with order n, we give some bounds on distance spectral radius and characterize the extremal graphs with such bouds; the spread of the complete graph Kn is proved to be the least, and the spread of bipartite graph K[n/2][n/2] is proved to be the least among all connected bipartite graphs.(5) In Chapter 5, we investigate the properties of the power sequence of a sign pattern matrix. In the first section, some basic definitions, notations and working lemmas are introduced. In the second section, the Lewin index extremal graph with both order n and girth 2 or 3 is characterized. In the third section, we determine the base set for the primitive nonpowerful sign pattern matrices with just d diagonal nonzero entry and determine the ex-tremal sign pattern matrix with both the maximal base and the least number of arcs. In the fourth section, we determine the base set for the primitive nonpowerful zero-symmetric sign pattern matrices without nonzero diago-nal entry and determine the extremal sign pattern matrix with the maximal base. In the last section, we give some bounds for the primitive nonpowerful sign pattern matrices, show that there are some new "gaps" in the base set and characterize some matrices with given some bases.