Study On Network Reliability: Graphs With Higher Order Connectedness

With the rapid development of communication networks, many theoretical problems have come into focus, one of which is the reliability of the network. Symmetry is also an important consideration, since symmetric networks posses many desirable properties. A network is often modelled as a graph. The classical measure of the reliability is the connectivity and the edge connectivity. For further study, many variations have been introduced, which are known as higher order connectedness, such as super-connectedness, hyper-connectedness, super-A, r-restricted edge connectivity, etc. This dissertation studies graphs, especially symmetric graphs, with higher order connectedness.In the first chapter, the background and some basic results are introduced. In the second chapter, we study higher order edge connectivity, and obtained (a) except for three graphs, all infinite circulants with finite jump sequence are super- ; (b) except for three classes of graphs, all edge transitive graphs are optimally- (3); (c) the optimally- (3) property is characterized for vertex transitive graphs, in particular, necessary and sufficient conditions are give for Cayley graphs to be optimally- (3) (d) a sufficient condition for a graph to be optimally- (3) is given. In chapter three, we study graphs with higher order vertex connectedness and (a) a characterization of edge transitive graphs which are super-connected or hyper-connected is given; (b) a new measure of network reliability, semi-hyper-connectedness, is proposed, and edge transitive graphs which are semi-hyper-connected are characterized. In the last chapter, we use the results of higher order edge connectivity to study the tree decomposition of transitive graphs, deriving a sufficient condition for a graph to have tree number equivalent to the arboricity.In studying higher order connectedness, the non-intersection of (edge) atoms is the key and the most difficult part to obtain. The successful application of higher order connectedness on tree decomposition leads us to seek further implementation of higher order connectedness to other branches of graph theory.