Researches On Network Reliability And Graph Connectivity

With the rapid development of Computer Science and Technology,networks have become an indispensable and important part of people’s lives.In topological sense,the network can be represented as a graph in Graph Theory.The connectivity of a graph is a significant parameter to evaluate the reliability of the corresponding network.It is a very meaningful work to study the structural characteristics of graphs with high connectivity for network reliability design and evaluation.We put forward our investigation in terms of topological indices of graphs.Firstly,we focus on exploring the structural properties of networks with k-connectivity as well as some related problems.In Chapter 1,we introduced the background and the process of the investigation related to this thesis as well as our main results obtained.In Chapter 2,we mainly considered the structural properties of a class of tree networks with a given degree sequences π,and proved that the BFS-tree T*is the unique tree which attains the largest generalized Randic index.In Chapter 3,we first analysized the k-connectivity of the network in terms of the well-known topological,the Forgotten index,and prove that any connected graph G with n vertices must be k-connected(k≤n-1)if satisfying F(G)>(k-1)~3+(n-k)(n-2)~3+(k-1)(n-1)~3.The condition obtained can not be dropped.In Chapter 4,we investigated the k-Hamiltonicity of graphs,and present a sufficient condition in terms of the Forgotten index of a graph:Let G be a connected graph with n≥6 vertices,and k is a positive integer satisfies 0≤k≤ n-3.If(?) Then graph G is a k-Hamilton graph.In Chapter 5,we proposed a sufficient condition for a graph to be β-deletability and k-independence,respectively.The condition obtained can not be dropped.In the last part of the thesis,a detailed summary of our main work were involved,and several problems were also put forward for the further research.