Research On Graph Invariants As Well As Their Applications In Complex Networks

The real world is a complex system composed of a variety of subjects and relationships.With the development of science and technology,human beings gradually realize the complexity and systematicness of the world.For example,from a macro point of view,the revolution of communication technology has made different individuals,regions and countries more closely linked;from a micro point of view,scientists have also found that interacting cells can form rich phenomena and achieve more complex functions.These structures composed of individuals and "connections" can topologically be abstracted into complex networks.As a unified tool to describe these networks,graph and the properties of graph invariants play a key role in quantifying the topological properties of networks.From the perspective of using graph invariants to describe the topological property of complex networks quantitatively,the properties of graph invariants such as Randi? index,graph energy and spectral radius,as well as the similarity measurements and distance measurements based on graph invariants such as molecular topological index were studied.And an effective measurement method for quantitative analysis of the similarity and difference of network topology is obtained,which provides a new research idea for realizing skeleton extraction of large-scale complex networks.The main work is as follows:(1)The minimal energy of tricyclic signed graphs which is an abstract model of symbol network was studied.We put forward a new classification method of tricyclic signed graphs,and established the relationship among the energy of tricyclic signed graphs,the energy of signed tree,the energy of unicyclic signed graphs and the energy of bicyclic signed graphs.The structures that there does not exist in tricyclic signed graphs with minimal energy were concluded,which provided a new method and necessary conclusions for solving further the conjecture of connected graphs with minimal energy.At the same time,it provides a new theoretical basis for quantitative analysis of the topological properties of symbol networks.(2)The AG matrix of graph was studied.The upper and lower definite bounds of the AG spectral radius and the AG energy,as well as the corresponding extreme graphs were described.On these basis,the Nordhaus-Gaddum-Type relation of the AG spectral radius and the Nordhaus-Gaddum-Type relation of the AG energy,as well as the corresponding extreme graph were further described.It will provide a new matrix representation for the topological structure of complex networks,a new research idea and theoretical guidance for further describing the topological properties of complex networks.(3)Taking cactus graphs as the research object which is classical model of loop networks,the Randi? index of cactus graphs was studied.The extremum on Randi? index of cacti with r cycles was solved,and the corresponding extreme graph were characterized.A new method using symmetric and asymmetric edges to depict the structure of cacti with large Randi? index was proposed.It will lay theoretical foundation for describing the topological properties of loop networks and provide a novel theoretical method for skeleton extraction of large-scale networks.(4)The similarity measurements and distance measurements based on graph invariants were studied.The smoothness of graph invariants,such as arithmrtric-geometric index,inverse sum indeg index and symmetric division deg index,Mostar index,Wiener index and graph energy were analyzed quantitatively.Similarity measurements and distance measurements of graphs were constructed based on four molecular topological indices which can capture different structural information of graphs.The numerical results show the domain coverage ability of these measurements,which can provide effective measurement indexes for quantitative analysis of the similarity and difference in the topology structure of network.