| With the development and wide application of network,the invulnerability of oriented graph has gradually become a hot issue in graph theory.Connectivity measures the difficulty of destroying a network,and burning number considers the process of burning the whole network in several discrete periods.In practice,it is necessary to consider the degree of network destruction in discrete periods,so it is of great significance to study the invulnerability of network by combining the burning number and connectivity with the oriented graph.In this thesis,the concept of burning connectivity of oriented graph is put forward by analyzing the research of burning number and connectivity.Firstly,the parameter calculation formulas of some special graphs and their deleted point(arc)subgraphs,trees,Cartesian product graphs of paths and paths are given.On this basis,the bounds of the burning connectivity of oriented graphs of general graphs and cyclic graphs,and the bounds of the burning connectivity of generalized directed Kautz graphs and generalized directed De Bruijn graphs are studied and given.Secondly,in the aspect of network invulnerability design,the extreme value graph and construction method in the meaning of burning connectivity are studied and given.On the basis of the above research,a polynomial time algorithm for burning connectivity of oriented graphs of general graphs is designed.Finally,the relationship between the burning connectivity of the oriented graph and the invulnerability of the network is studied.The burning connectivity of oriented graph proposed in this thesis can accurately measure the difficulty of destroying a network in discrete time periods,and it is the optimization and improvement of connectivity and burning number.In particular,the oriented graph is taken as the research object,which is more suitable for the actual network.Through algorithm design and complexity analysis,it is shown that the burning connectivity of oriented graph is solvable for general graphs. |
