The Applications Of Graph Theory In Complex Networks And The Research On Graph Invariants

With the continuous development and progress of science and technology,society has officially entered the network era,and people need to contact and deal with more and more complex networks.As a special form of data representation and the structural form of complex system,complex network is composed of nodes and edges,which is an abstract description of complex system.Graph is a tool from the topological point of view,and many properties of its invariants play a significant role in the study of the properties of complex network topology.There are many kinds of graph invariants,among which the most important ones are topology index,graph energy and graph entropy,etc.,which can well reflect the properties of topology structure of complex network.For example,graph invariants can reflect the local characteristics of complex networks.Important nodes of complex networks can be effectively identified,and their importance can be sorted,so that important nodes of complex networks can be protected.In the field of computer science,graph theory can be used in complex network,programming and algorithm theory.Therefore,we can learn from many excellent research methods and fruitful achievements in graph theory to study complex networks.In short,graph theory has become a powerful tool for solving complex network problems.In this paper,the properties of topology structure of complex network are studied by using the graph invariants,and the properties of graph invariants such as topological index and graph energy are also studied.The main work is as follows:(1)This paper introduces several classic attack strategies,and then puts forward four new attack strategies:GA(G)centrality,AG(G)centrality,Lz(G)centrality and R(G)centrality.Finally,four new attack strategies are compared with several classical attack strategies in the same network.The study found that the other three new attack strategies are more efficient than the traditional attack strategies except that the R(G)centrality can not measure the importance of nodes well.(2)In this paper,we prove the correctness of the conjecture by Prof.Yanling Shao et al.(TheP_n of order n which has the maximal geometric-arithmetic energy among all trees of order n),obtain the upper bound of geometric-arithmetic energy of the tree,and characterize the extremal graph.Finally,the lower bound of geometric-arithmetic energy of the trees is obtained and the extremal graph is characterized.(3)The bounds of the arithmetic-geometric exponents and the arithmetic-geometric energies are studied from the algebraic point of view.Some new upper and lower bounds of arithmetic-geometric exponents and arithmetic-geometric energies of graphs are obtained,and extremal graphs are characterized.(4)The research background and significance of Lanzhou index is introduced.Firstly,the calculation method of Lanzhou index with perfect matching tree in given diameter is obtained.Finally,the upper and lower bounds of Lanzhou index with perfect matching trees are obtained by graph transformation and fractional comparison,and the extremal graph is described.(5)The coral tree set T(n)is defined in this paper.The upper bound of Randi(?)energy of the coral tree is obtained by graph transformation and fractional comparison,and the extremal graph is described.Then present the graph G of order n is satisfied the conjecture proposed by Gutman et al.that the connected tree T has maximal Randi(?)energy,and get the coral tree set T(n)is satisfied the conjecture proposed by Gutman et al..Therefore,this paper makes a modest contribution to further solving the conjecture proposed by Gutman et al.