A Study Of Edge Neighbor Toughness Of Graphs

Networks in the information age are closely related to people's life,work,study and so on.No matter which kind of network's interruption will cause significant losses.Therefore,the research of network invulnerability is particularly important.Network invulnerability is divided into two categories: non-neighbor invulnerability and neighbor invulnerability.The non-neighbor invulnerability research is relatively early,and there are many research results.The neighbor invulnerability research started late and has not yet formed a system.The edge neighbor toughness is an important neighbor invulnerability parameter of networks.This paper studies the related problems of analysis and design of this parameter.Firstly,the rationality of the definition of the edge neighbor toughness is demonstrated by examples.The important role of the edge neighbor toughness for the graph structure characterization is revealed by analyzing the properties of the edge neighbor toughness and its relationship with other invulnerability parameters.Using mathematical reasoning and proof,the calculation formula or bounds of the edge neighbor toughness of some special graphs and operation graphs are obtained.By constructing a class of special graphs,the edge control number problem of a complete bipartite graph and the edge neighbor toughness problem of general graphs can be transformed into each other in polynomial time,which proves the NP completeness of computing the edge neighbor toughness of general graphs.By studying the structure characteristics of trees in the sense of the edge neighbor toughness,a polynomial time algorithm for the edge neighbor toughness of trees is given.In the part of optimization of network structure in the sense of the edge neighbor toughness,the Nordhaus-Gaddum type problem is studied firstly,and the NordhausGaddum type inequality of edge neighbor toughness is given.The concept of minimally t-edge neighbor tough graph is proposed,the structure characteristics of minimally1-edge neighbor tough graph is analyzed,and a sufficient condition for the minimally1-edge neighbor tough graph to be Hamiltonian is given.In addition,several special minimally t-edge neighbor tough graphs are found,and a class of minimally t-edge neighbor tough graphs are constructed.This paper solves some basic problems about the edge neighbor toughness of graphs.The research methods and conclusions have certain reference for the further study of neighbor invulnerability of networks.