Study On Topological Indices Extremal Graphs And Related Problems

The contents of graph spectral theory have important applications in theoretical chemistry,especially in studying the chemical compounds reactivity,stability and exis-tence of Huckel molecular orbital model and other chemical properties.Based on these applications,graph spectral theory has been studied extensively by many researchers.The rank of the adjacency matrix and other topological indices are not only invariants of graphs but also important spectral parameters,which is one of hot topics in graph spectral theory.The research methods of the ranks and many other topological indices of graphs can permeate each other.The ranks of the adjacent matrices of some kinds of graphs and some related topological indices are studied in this paper.As an invariant of a graph,the connectivity of a graph not only intersects with the study of the graph topological indices,but also has a close relation with many graph parameters such as matching number and the spectral theory of graphs.This dissertation focuses on the s-tudy of the relationships among the ranks of adjacency matrices of some kinds of graphs and some graph parameters such as matching number,independence number and some topological indices,the necessary and sufficient conditions for the extremal graphs with upper and lower bounds of the ranks are obtained.Moreover,the edge-Szeged indices of some kinds of graphs and the strong Menger connectedness of regular graphs are investigated.The rest of this dissertation is organized as follows:In Chapter 1,some backgrounds are introduced firstly.Then the research status of related fields are characterized.Finally,the main results of this dissertation are present-ed.In Chapter 2,some basic definitions and notations used in this dissertation are presented.In Chapter 3,we study the lower and upper bounds for the rank of a signed graph in terms of the matching number.And prove that 2m(G)-2c(G)?r(G,?)?2m(G)+c(G),where r(G,?)is the rank of adjacency matrix of the signed graph(G,?),m(G)and c(G)are the matching number and cyclomatic number of the base graph G of the signed graph(G,?),respectively.Moreover,the extremal signed graphs which reach the lower bound and the upper bound are characterized,respectively.Furthermore,the exact number of the positive and negative inertia indices of the mixed unicyclic graphs and the upper and lower bounds of the positive and negative inertia indices of the mixed graphs in terms of the matching number are given,respectively.In Chapter 4,we study the lower and upper bounds for the rank of a complex unit gain graph in terms of the matching number and the independent number are given respectively.And prove 2m(G)-2c(G)? r(G,?)?2m(G)+c(G)and 2|V(G)|-2c(G)?r(G,?)+2?(G)? 2|V(G)|,where r(G,?)is the rank of adjacency matrix of the complex unit gain graph(G,?)and ?(G)is the independence number of the base graph G of the complex unit gain graph graph(G,?)respectively.Moreover,the properties of the extremal complex unit gain graphs which attended the lower and upper bounds are investigated,respectively.The results of this chapter generalize the corresponding results about undirected graphs,mixed graphs,directed graphs and signed graphs in literatures.In Chapter 5,the lower bounds of the edge-Szeged index and the edge-vertex-Szeged index for cacti with order n and k cycles are determined,and the properties of all the graphs that achieve the lower bounds are identified.Moreover,the minimum number of the edge-Szeged index among all the unicyclic graphs with perfect matchings is investigated.In Chapter 6,a unified approach by considering various sufficient conditions of a regular graph to be F-strongly Menger connected of order r is developed which gen-eralize the corresponding results about r=2.As corollaries,the F-strongly Menger connectedness of order r of several interconnection networks are presented.In Chapter 7,this dissertation is summarized and several problems for further re-search are given.