Research On Extremal Problems Based On Some Graphic Parameters

Graph theory has been used extensively in almost all fields including physic,chemistry,computer science, it promotes extremely the development of graph theory, at the same time, many new challenging problems have arisen. Extremal problem based on some graphic parameters is one of the hot problems in graph theory.The energy of a graph is defined as the sum of the absolute values of all the eigenvalues of the graph. The Hosoya index and Merrifield-Simmons index are the total number of its matchings and the the total number of its independent sets, respectively. The largest eigenvalue corresponding to the matrix of a graph is called the spectral radius of the graph. In this dissertation, we study the extremal problems based on some graphic parameters, such as energy of a graph,Hosoya index,Merrifield-Simmons index,spectral radius. The mainly works of this paper are as following.Firstly, by an analysis of the structure of trcyclic graph in depth, we prove that the conjecture, which is proposed by Caporossi et al., holds, by induction, for tricyclic graphs which contain no disjoint odd cycles Cp,Cq of lengths p and q with p+q≡2 mod(4), and characterize the minimal and second-minimal energies of graphs in it. At the same time, we also study unicyclic graphs, and characterize the corresponding extremal graphs with the fourth-,fifth- and sixth-minimal energies.Secondly, we study the extremal problems mainly on graphic parameters:Hosoya index and Merrifield-Simmons index. We characterize completely the corresponding extremal graphs for bicyclic graph,tricyclic graph,θ-graph and unicyclic graph given diameter.Thirdly, we consider the extremal problems mainly on graphic parameters: Laplacain spectral radius,Signless Laplacain spectral radius and reciprocal distance spectral radius. For each spectral radius, we obtain the upper bound for the corresponding spectral radius, and characterize completely the corresponding extremal graphs for tricyclic graph given girth,bicyclic graph given girth and simple connected graphs with n vertices and with given matching number, respectively.