κ-Restricted Edge Connectivity Of Graphs

The interconnected network topology of a multiprocessor system is usually modeled by a graph as a mathematical model, in which the vertices in the graph represent pro-cessors and edges represent the direct communication links between processors. We can measure the performance of network topology by the properties of graphs. The reliability of networks can be denned as the ability to keep networks connected and meet the require-ments of communication under the given conditions. The κ-restricted edge connectivity is an important parameter of measuring the reliability of networks. Let G be an undirected, simple and connected graph and let S be a edge cut of G. S is called a κ-restricted edge cut of G if G-S is disconnected and every component of G-S has at least k vertices. G is called a λκ-connected graph if κ-restricted edge cut of G exists. The κ-restricted edge connectivity of G, denoted by λκ(G), is defined as λκ(G)=min{|S|:S is G a κ-restricted edge cut}. λκ-cut of G is defined as the κ-restricted edge cut with the minimum cardinal-ity. Denote ξκ(G)=min{|[X,(?)]|:X C V(G),|X|=κ, G[X] is connected}. G is called a maximally κ-restricted edge connected graph if λκ(G)=ξκ(G). Furthermore, G is called a super κ-restricted edge connected graph if every minimum κ-restricted edge cut of G isolates one connected subgraph with order k. Generally speaking, the network with the topology based on a maximally κ-restricted edge connected graph or a super κ-restricted edge connected graph is more reliable.This paper discusses the maximally κ-restricted edge connectivity and super k-restricted edge connectivity of graphs on the basis of the previous work. This thesis consists of three chapters.In Chapter1, a survey on the application background and the research advance of k-restricted edge connectivity of graphs is given. Meanwhile, some definitions and notations used in this thesis are introduced.In Chapter2, degree conditions for graphs to be maximally κ-restricted edge con-nected and super κ-restricted edge connected are given and the following results are ob-tained:(1) Let κ>2be an positive integer and let G be a λκ-connected graph with order v(G)> κ(κ-1). If G satisfies (a) and (b), then G is maximally κ-restricted edge connected.(a) max{dG(u), dG(v)}≥[v(G)/x]+κ-2m+1for each pair u, v∈V(G) when the distance da(u, v)=m, where2≤m≤k; (b)for any subgraph H of G which is isomorphic to KK+1,there exists at least one vertex v∈v(H)such that dG(v)≥[v)(G)/2]+κ-1.(2)Let κ≥2be an positive integer and let G be a λκ-connected graph with order v(G)>κ(κ-1).If G satisfies(a)and(b),then G is super κ-restricted edge connected.(a)max{dG(u),dG(v)]}≥[v(G)/2]+κ-2m+2for each pair u,v∈V(G)when the distance dG(u,v)=m,where2≤m≤κ(b)for any subgraph H of G which is isomorphic to KK+1,there exists at least one vertex v∈V(H)such that dG(v)≥[v(G)/2]+κ.In Chapter3,suffcient conditions for bipartite graphs to be maximally κ-restricted edge connected are given and the follwing results are obtained:(1)Let G=(X∪Y,E)be a bipartite graph with orderv(G)≥8andξ4(G)≤[v(G)/2]. If G has a matching that saturates all vertices in X or all vertices in Y and|N(u)∩(v)|≥4for each pair u,v∈X or u,v∈y,then G is maximally4-restricted edge connected.(2)Let κ≥2be an positive integer and let G=(X∪Y E)be a connected bipartite graph with orderv,(G)≥2κ.Let[U,U]be a λκ-cut of G.Denote U*={v∈U|[v,U]|≤κ-1/2}.If G satisfies|N(u)∩N(v)|≥κ for each pair u,v∈X or u,v∈Y and d(u)≥[v(G)/2]-1for any u∈U*when|U*|>[κ/2],then G is maximally κ-restricted edge connected.(3)Let2≤κ≤δ+1be an positive integer and let G=(V’∪V",E)be a connected bipartite graph with order v(G)≥2(δ+1).If ther.e exists a λκ-cutS=[X,X]satisfying|X|≤|(?)|XV’|≤[v(G)/4] and|X∩V"|≤[v(G)/4] and G satisfies dG(x)+dG(y)≥2[v(G)/4]+2κ-2for each pair x,y∈V(G)when the distance dG(x,y)=2,then G is maximally κ-restricted edge connected.