A Characterization Of Two Graphs With Low Rank

Spectral graph theory is an important branch in graph theory, which mainly character-izes the structural property of graphs by using their spectral property. The nullity or rank problems of graphs are hot issues of spectral graph theory in recent years. The nullity of a graph is defined as the multiplication of zero eigenvalue of its adjacent matrix. In quantum chemistry, when Erich Hiickel dealt with a class of special organic molecules-unsaturated hydrocarbon, he posed Hiickel Molecular Orbital theory, or HMO theory[14]. This theory reveals the connection between the chemical stability of unsaturated hydrocarbon and the nullity of its molecular structural graph, which opens a door of studying nullity of graphs. In1957, Collatz and Sinogowitz[8] posed the problem of characterizing all singular graphs, it became a hot issue in mathematics since then.Now the nullity or rank problems arc still attracting much attention. Except the de-termination of nullity set for certain graphs, there are still several work characterizing the graphs with given rank or nullity. For instance, it is known that a graph is complete bipartite if and only if its rank is2, and a graph is complete tripartite if and only if its rank is3[6]. Thus we are interested in characterizing the graphs with given rank k. Gerard J. Chang, Liang-Hao Huang, and Hong-Gwa Yeh[4,5] recently have characterized all reduced graphs with rank4or5. So it is a natural problem of characterizing all reduced graphs with rank6. Until now, there are progresses merely for special graphs. For example, Yi-Zheng Fan [17] characterizes the regular bipartite graphs with rank6.In the first Chapter of this paper, we introduce the background of spectral graph theory and the problems of nullity, show the related definitions and notations in this paper. We also introduce the research progress during recent years. The second Chapter is the main content in this paper, we characterize all connected reduced triangle-free graphs with rank6. In the last Chapter, we use the main theorem and methods in this paper to give characterization of unicyclic graphs with rank6or7, as an application and subsequent work of the main results.