Studies On Some Network Invulnerability And Neighbor Invulnerability Parameters

Network invulnerability is an important research topic of disciplines such as Computer Science, Logistics Science, Operations Research, etc.Network era witnesses the fact that more and more attentions have been paied to network invulnerability.In the design of computer and communication networks, invulnerability must be considered in order to avoid or decrease the loss caused by communication interrupt.Therefore, one of the basic ideas in designing networks is that they do not easily be disrupted and can easily repaired once disrupted.These networks are often modeled by connected graphs, where the vertices represent the communication stations and edges represent the communication links.The invulunerability of general network is the corresponding graph’s invulunerability that described quantitatively by introducing appropriate parameters.Connectivity and edge-connectivity are two parameters often used to measure the vulnerability of graphs.It is well known that both of them can be computed in polynomial time.In recent decades, some new vulnerability parameters have been introduced because of the limitations of connectivity and edge-connectivity.In this dissertation, we study some invulnerability parameters and neighbor invulnerability parameters of graphs based on the existing research.The text consists of five chapters and the arrangements are as follows.The first chapter is the brief introduction of the concepts, the research background and the main results of network invulnerability.In Chapter 2, we introduce the average(edge)-toughness and the average(edge)-tenacity of graphs.Moreover, we provide the computing formula on these parameters of some specific classes of graphs.The average vertex(edge)-neighbour-toughness and the average vertex(edge)-neighbour-tenacity of graphs are studied in Chapter 3.Besides, we provide the computing formula on these parameters of some specific classes of graphs.A concept of honest weighted graph based on the invulnerability parameters of weighted graphs is introdued in Chapter 4.Furthermore, we considers some related problems.In Chapter 5, we summarizes this dissertation and proposes several problems worthy of further research.