Conditional Connectivity For Some Important Classes Of Graphs

The connectivity and edge connectivity axe important measure of the network's reliability. As a generalization of classical (edge) connectivity, the concept of conditional (edge) connectivity has been proposed. In this thesis, we study the conditional (edge) connectivity for some important classes of graphs.In chapter one, we introduce the background and terminology. Chapter two is devoted to studying super-edge-connected and optimally super-edge-connected Bi-Cayley graphs. Let G be a finite group, 5(possibly, contains the identity element) be a subset of G. The Bi-Cayley graph BC(G, S) is a bipartite graph with vertex set G × {0,1} and edge set {{(g, 0), (gs, 1)}, g ∈ G, s ∈ S}. A graph X is said to be super-edge-connected if every minimum edge cut of X is a set of edges incident with some vertex. The restricted edge connectivity λ'(X) of X is the minimum number of edges whose removal disconnects X into nontrivial components. A k-regular graph X is said to be optimally super-edge-connected if X is super-edge-connected and its restricted edge connectivity attains the maximum 2k — 2. In chapter two, we show that all connected Bi-Cayley graphs, except even cycles, are optimally super-edge-connected.In chapter three, we study the edge connectivity of k-regular connected graph with two orbits. The following results are obtained: (a) The edge connectivity of 3-regular and 4-regular connected graphs with two orbits is determined; (b) we prove the existence of k-regular m-edge-connected graphs with two orbits for some given positive integers k and m; (c) The edge connectivity of a k-regular connected graph with two orbits and girth ≥ 5 attains its regular degree k.In chapter four, we study the second isoperimetric connectivity of line graphs and line digraphs. For line digraphs, we show that the second isoperimetric connectivity of strongly connected line digraphs with δ ≥ 2 equals its connectivity. For line graphs, we give a sufficient and necessary condition for the existence of the second isoperimetric connectivity, and we show that under the condition that the second isoperimetric connectivity exists, the second isoperimetric con-...