Higher Order Connectedness Of A Graph

With the rapid development of information networks,many theoretical problems come into focus,one of which is the reliability of the network,that is,the ability of the network to function even when some vertices and/or edges fail.The underlying topology of a network is often modeled as a graph or a digraph.So,some classical notations of graph theory,such as the connectivity and the edge-connectivity,is utilized to measure the reliability of networks.For further study,many variations have been introduced, which are known as higher order connectedness,such as super-κ,hyper-κ,restricted edge connectivityλ_k(G),super-restricted edge connectivity,etc.This thesis is divided into four chapters.In Chapter 1,we introduce the background of our study and some notation.Then we state the main results in this thesis.In Chapter 2,we give a sufficient condition for a graph to beλ_k-optimal,which is an improvement over previous results.In Chapter 3,we computeλ_k,andξ_k for Harary graphs and completely characterized allλ_k-optimal of Harary graphs.In Chapter 4,we study restricted vertex connectivity,κ_k andκ'_k,whereκ'_k is a new graph parameter proposed by us.We show thatκ'₂(G) is a quantitative measure for hyper-connectedness,and give some sufficient conditions for the existence of and upper bound forκ_k and/orκ'_k.We also studied some properties ofκ_k andκ'_k,and give out a relation between them.