A Study On The Toughness And Neighbor Tenacity Of Weighted Graphs

With the development of the network and the complexity and change of the external environment,the research of network invulnerability becomes particularly important.In the process of network maintenance and design,we should improve its ability to resist external attacks such that the network interruption can be quickly repaired.With the deepening of the research,it is found that the invulnerability parameters of non-weighted graphs have obvious shortcomings in describing the invulnerability of the network.The actual network is essentially a weighted graph,so consider the invulnerability of the weighted graph is more practical.Based on the summarize and compare of the invulnerability parameters of nonweighted graphs,two new parameters are introduced which can objectively describe the invulnerability of weighted graphs-weighted toughness and the weighted neighbor tenacity.The properties of obtained cut and local minimum cut of interval graph are studied.On this basis,an algorithm for computing the weighted toughness of interval graphs is designed,and the complexity of the algorithm is analyzed.The definition of weighted neighbor tenacity of graph is given.The maximum or minimum values of weighted neighbor tenacity of special structure graphs such as roads,circles,wheel graphs,star graphs are studied and given.Two types of composite star graphs are constructed,using mathematical modeling methods,the extreme value of this parameter and the structure of the corresponding graph are studied and given.The research shows that these two new parameters can better describe the invulnerability of weighted graphs,and are more in line with the actual situation than other parameters.