Complete Characterization Of Graphs With Exactly Two Positive Eigenvalues

Algebraic graph theory is an important area of research in graph theory,it is widely used in various fields,such as life sciences,computer networks,combinatorial optimiza-tion,biochemistry,molecular theory.Spectral graph theory is an important topic in algebraic graph theory,it focuses on the algebraic and combinatorial parameters,such as characteristic polynomials,eigenvalues and eigenvectors of matrices associated with graphs by using matrix theory,combinatorial design and group theory,and investigates the relations between these parameters and the structure of graphs.Therefore,the spectral determination of a graph is an main topic of spectral graph theory,it investi-gates the structure property of a graph by means of it's spectrum.Thus the problem of characterizing graphs with a few positive eigenvalues(small positive inertia index)is important and interesting.In 1977,Smith^[44]proved that the disjoint union of a com-plete multipartite graph and some isolated vertices are the only graphs with exactly one positive eigenvalue.This assertion has been widely used in the research of spectral graph theory.But up till now,the characterization of graphs with exactly two positive eigenvalues is only completed in some cases.In this paper,we completely characterize the graphs with exactly two positive eigenvalues.This thesis can be divided into six chapters,we give a brief introduction of each chapter as below.In Chapter 1,we first describe the background of spectral graph theory;next we introduce some basic notions and symbols;finally,the research progress of related problems involved in this thesis and the main results of the thesis are listed.In Chapter 27 we introduce the congruent transformations of graph of ?-,?-,?-and ?-type,and we give some properties of these congruent transformations of graph by using the property of congruent transformation of matrix.In particular,the congruent transformations of graph of ?-,?-,and ?-type are also mentioned in other articles,but the congruent transformation of graph of ?-type is our original definition.Let T_n⁰ be the set of graphs of order n with two positive eigenvalues and no nullity.In Chapter 3,we introduce some definitions of Oboudi^[37],and we look back the char-acterization of graphs in T_n⁰ which is proved by Oboudi.In fact,the author proved that T_no consists of 48 infinite families of graphs(see Table 6.1)and other 601 specific graphs,and we list these infinite families in Chapter 4.Let T_n¹ be the set of graphs of order n with two positive eigenvalues and one nullity.In Chapter 4,we completely characterize the graphs in T_n¹.By applying the congruent transformations of graph of ?-,?-,?-and ?-type,and the graphs in T_n⁰,we can construct the sets T_n¹(?),T_n¹(?),T_n¹(?)and T_n¹(?)of graphs in T_n¹.It is clear that the graphs of T_n¹(?),T_n¹(?):T_n¹(?)and T_n¹(?)are determined by that of T_n-10.First,we prove that the disconnected graph of T_n¹ belongs to T_n¹(?)or T_n¹(?).Next,we can divide the connected graphs of T_n¹ into three classes by using the special induced subgraph of the connected graph in T_n¹.And we prove that the connected graphs of T_n¹,except for a finite number of graphs,belong to T_n¹(?),T_n(?)or T_n¹(?).In fact,T_n¹ consists of the graphs in T_n¹(?),T_n¹(?),T_n¹(?)and T_n¹(?),and other 802 specific graphs(see Table 6.1).Let T_n^s be the set of graphs of order n with two positive eigenvalues and s(2?s?n-3)nullit,ies.In Chapter 5,we further characterize the graphs in T_n^s.Similar to Chapter 4,by applying the four congruent transformations of graph and the graphs in T_n¹,we can recursively construct the sets T_n^s(?),T_n^s(?),T_n^s(?)and T_n^s(?)of graphs in T_n^s.Since the structure of graph in T_n^s are similar to that of the graph in T_n¹,we characterize the graphs of T_n^s by a similar manner as Chapter 4.In fact,T_n^s consists of the graphs in T_n^s(?),T_n^s(?)and T_n^s(?),and other 175 specific graphs(see Table 6.1).In Chapter 6,we give a summary about the proof and manner since there are many concepts and symbols in this paper.Let T_n be the set of graphs of order n with two positive eigenvalues.Then T_n=U_s=0^n-3T_n^s.We give the definitions of constructible graph and nonconstructible graph to divide the graphs in T_n.In fact,the graphs of T_n^s(?),T_n^s(?):T_n^s(?)and T_n^s(?)(1?s?n-3)are constructible,and the graphs of T_n⁰,and 802 specific graphs of T_n¹,and 175 specific graphs of T_n² are nonconstructible.Thus T_n is the disjoint union of constructible graphs and nonconstructible graphs.In addition,we give an example to illustrate the construction of graphs in T_n.Finally,we give some future work by using the graphs of T_n.