On Super Restricted Edge Connectivity And Lower Bounds On The Edge-Connectivity Of Graphs

Graphs are ofen as models for the multiprocessor interconnection networks. Let G be an undircted, simple and connected gragh. A restricted edge-cut F of G is an edge-cut such that G-F has no isolated vertex. The restricted edge-connectivity is the minimum cardinality over all restricted edge-cuts. The restricted edge connectivity, as a generalization of classical edge connectivity, is an important measure of fault-tolerance for interconnection networks. The super restricted edge connectivity provides a more accurate index of fault-tolerance than the restricted edge-connectivity. G is called a super restricted edge connected graph if every minimum restricted edge cut separates exactly one edge of minimum edge degree. In this thesis, we mainly study the super restricted edge connectivity in graphs of diameter 2 and lower bounds on the edge-connectivity of digraphs.In Chapter 1, after a short introduction to the used basic notation and terminology on graphs, we give in Section 1.2 some concepts and results on edge connectivity.In Chapter 2, we deal with the super restricted edge connectivity for graphs of diameter 2. In Section 2.1 we provide several simple, but very useful facts and summarize the known results on connectivity of graphs of diameter 2. In section 2.2, some sufficient conditions for super restricted edge connectivity in graphs of diameter 2 are given as follows.(1)Let G be a graph of order v(≥4). If |N(x)∩N(y)|≥3 for all pairs x,y of nonadjacent vertices, and |N(u)∩N(v)|≥2 for all pairs u,v of adjacent vertices, then G is a super restricted edge connected graph unless G belongs to an especial graph-class.(2)Let G be a graph of order v(≥4). G[N(u)∩N(v)] contains at least three edges for all pairs u, v of nonadjacent vertices, then G is a super restricted edge connected graph unless G belongs to an especial graph-class.(3)Let G be a graph of order v(≥13). If |N(u)∩N(v)|≥3 for all pairs u,v of nonadjacent vertices and minimum edge degreeξ(G)≥(?)v/2」+ 2, then G is a super restricted edge connected graph.(4)Let G be a graph of order v(≥10) and minimum degreeδ(G)≥3. If |N(x)∩N(y)|≤1 for all pairs u,v of adjacent vertices, and |N(u)∩N(v)|≥2 for all pairs u, v of nonadjacent vertices, then G is a super restricted edge connected graph unless G belongs to an especial graph-class.In Chapter 3, we study lower bounds on the edge-connectivity of digraphs, orientedgraphs and oriented bipartite graphs, Results are given as follows. (5)Let D be a strongly connected digraph of order v(≥4), edge-connectivityλ(D), minimum degreeδ(D) and minimum arc degreeξ(D). Ifλ(D) <δ(D), then(6) Let D be a strongly connected oriented graph of order v(≥6), edge-connectivityλ(D), minimum degreeδ(D) and degree sequence d₁≥d₂≥…≥d_v. Ifλ(D)≤δ(D)- k for some integer k with 0≤k≤δ(D), then(7)Let D be a strongly connected oriented bipartite graph of order v(≥6), edgeconnectivityλ(D), minimum degreeδ(D) and degree sequence d₁≥d₂≥…≥d_v. Ifλ(D)≤δ(D) - k for some integer k with 0≤k≤δ(D), then...