On Optimal Problem Of 3-restricted Edge Connectivity In Graghs

For an undircted, simple and connected gragh G=(V, E), An edge set S(?)Eis a k-restricted edge-cut if G-S is disconnected and every component of G-Shas at least k vertices. The k-restricted edge-connectivity of G, denoted byλ_k(G),isdefined as the minimum cardinality over all k-restricted edge-cuts. The k-restrictededge connectivity, as a generalization of classical edge connectivity, is an importantmeasure of fault-tolerance for interconnection networks. The optimal k-restrictededge connectivity provides a more accurate index of fault-tolerance of networks. In thisthesis, we mainly study some sufficient conditions for the existence ofλ_k-connectivityand optimal problem of 3-restricted edge connectivity in graphs of diameter 2.In Chapter 1, after a short introduction to the used basic notation and terminologyon graphs, we give in Section 1.2 some concepts and results on the k-restricted edgeconnectivity.In Chapter 2 we mainly study some sufficient conditions forλ_k-connectivity ingraphs of diameter 2, and we provided sufficient conditions for the existence ofλ_k-connectivity in completed Graphs.Chapter 3 deals with the optimal restricted edge connectivity for graphs of diam-eter 2. In Section 3.1 we provide several simple, but very useful facts and summarizethe obtained results on connectivity of graphs of diameter 2. In Section 3.2, somesufficient conditions for optimal 3-restricted edge connectivity in graphs of diameter2 are given as follows.(1)Let G beλ₃-connected gragh. If |N(u)∩N(v)|≥4 for all pairs u, v of nonadjacentvertices such that neither u nor v lie on a triangle, and |N(u)∩N(v)]≥5 for all pairsu, v of nonadjacent vertices with the property that u or v are on a triangle, then G isλ_a-optimal.(2)Let G beλ₃-connected gragh. If |N(u)∩N(v)|≥4 and G[N(u)∩N(v)] containsat least 4 edge for all pairs u, v of nonadjacent vertices,then G isλ₃-optimal.(3)Let G beλ₃-connected gragh with |V(G)|≥38. If |N(x)∩N(y)|≥4 for all pairsu, v of nonadjacent vertices andξ₃(G)≤v+2, then G isλ₃-optimal.(4)Let G beλ₃-connected gragh satisfying |N(x)∩N(y)|≥4 for all pairs u,v ofnonadjacent vertices. If for each triangle T there exists at least one vertex v∈V(T)such thatd(v)≥[v/2]+2, then G isλ₃-optimal.