On The Super Connectedness And Restricted Connectivity Of Graphs

With the rapid development of information networks, many theo-retical problems come into focus, one of which is the reliability of thenetwork, that is, the ability of the network to function even when somevertices and/or edges fail. The underlying topology of a network is oftenmodeled as a graph. So, some classical notations of graph theory, suchas the connectivity and the edge-connectivity, is utilized to measure thereliability of networks. For further study, people propose many new con-cepts of connectedness, which have profound background in optimizationdesign of networks, such as super (edge) connectedness, restricted (edge)connectivity, etc. In this paper, we mainly study the super connected-ness of some kinds of vertex transitive graphs, the restricted connectivityof two kinds of Cartesian product graphs and minimal Abelian Cayleygraphs, and the restricted edge connectivity of mixed Cayley graphs.In chapter1, we introduce the background of our study and some no-tations, and recall the study of various kinds of connectivities. In chapter2, we characterize super connected small degree vertex transitive graphs(that is, the vertex transitive graphs with regularity less than7). As acorollary, we completely characterize the super connected vertex tran-sitive planar graphs. In chapter3, we give a sufcient condition for avertex transitive graph to be maximally connected. And characterizesuper connected3-diamond-free vertex transitive graphs. In chapter4,we study the restricted connectivity of two kinds of Cartesian productgraphs and minimal Abelian Cayley graphs. In chapter5, we studythe restricted edge connectivity of mixed Cayley graph, and give suf-cient and necessary conditions for mixed Cayley graphs to be optimal restricted edge connected.In this paper, superatoms, λ-atoms and their non-intersection arethe key for our argumentation. The main method for proving our resultsis by contradiction.