3-Restricted Edge Connectivity And 3-Restricted Connectivity Of Graphs

A network can be modeled as a graph, and the stability of the network can be measuredby various kinds of connectivities of the corresponding graph. We study one kind of themin this dissertation, which is 3-restricted-edge(vertex)-connectivity.An edge subset S of a connected graph G = (V,E) is a k-restricted-edge-cut if G ? Sis disconnected, and every component of G ? S has at least k vertices. The k-restricted-edge-connectivity of G, denoted byλk(G), is the cardinality of a minimum k-restricted-edge-cut. From recent studies on this parameter, it seems that the largerλk is, the morestable the network is. Defineξk(G) = min{ [U,U]| : ? = U ? V (G),|U| = k and G[U] isconnected}, where |[U,U]| is the number of edges with one end in U and the other end inU, U = V \U. In large number of cases,ξk(G) is an upper bound forλk(G). Hence it isdefined in the literature that a graph G is calledλk-optimal ifλk(G) =ξk(G).An vertex set X is a k-restricted cut of G, if G ? X is not connected and everycomponent of G ? X has at least k vertices. The k-restricted connectivityκk(G) (inshortκk) of G, is the cardinality of a minimum k-restricted cut of G. X is calledκk-cut,if |X| =κk.This dissertation is organized as follows. In Section 1.1, we introduce brie?y thebackground of this parameter, and some terminologies. Section 1.2 presents the mainresults. Section 2.1 is devoted to proving let G be aλ3-connected triangle-free graph. If|N(u)∩N(v)|≥3 for all pairs u, v of nonadjacent vertices, then G isλ3-optimal. Section2.2 is devoted to showing that let G be aλ3-connected triangle-free graph of order n≥6and degree sequence d1≥d2≥...≥dn =δ. Ifthen G isλ3-optimal. More generally, Let p≥3 be an integer, and let G be aλ3-connectedtriangle-free graph of order n≥6 with clique numberω(G)≤p, and degree sequenced1≥d2≥...≥dn =δ. Ifthen G isλ3-optimal. Chapter 3 is devoted to showing that let G be a connected graphwith girth g≥6, minimum degreeδ≥3 and diameter D. Suppose that there exists a2-path u0u1u2 with d(u0)+d(u1)+d(u2)?4 =ξ3(G) such that every cycle u0u1u2u3u4u5u0 (if any) satisfies d(u4)≥4. Thenκ3(G) =ξ3(G) if one of the following assertions holds :(1) D≤g ? 4.(2) g is even. D = g ? 3 and each pair u,v of vertices at distance d(u,v) = g ? 3 is suchthat neither vertex u nor vertex v lies on a cycle of length g.(3) g is even. |N(g?4)/2(u)∩N(g?2)/2(v)|≥3 for all pairs u,v of vertices at distanced(u,v)≥g ? 3.(4) g≥8 is even. Suppose that for all pairs u,v of vertices at distance d(u,v)≥g ? 3,the set N(g?4)/2(u)∩N(g?2)/2(v) contains at least two distinct vertices x1,x2 such that2≤d(x1,x2)≤(g ? 4)/2 and such that any w∈N(g?4)/2(v)∩(N(x1)∪N(x2)) satisfies...