Edge Isopermetric Problem On Graphs And The Related Applications

The edge isopermetric problem on the graph G is to find a subset with m vertices of G,such that the edge cut separating this subset from its complement has minimal size among all subsets of the same cardinality.Since it was proposed by Harper in 1964,it found extensively applications in the fields such as reliability evaluation of an interconnection network,minimum edge congestion and minimum wirelength of graph embedding,the technology of wavelength-division multiplexing In fiber-optic communications and the influence function of boolean function.For a given connected graph G and a positive integer h?(?)?V(G)?/2(?),the h-extra edge-connectivity was first introduced by J.Fabrega and M.A.Foil in 1996(also called h-restricted edge-connectivity.The h-extra edge-connectivity of G,if any,denoted by ?h(G),is the minimum cardinality of an edge set in G,satisfying whose removal disconnects G and every component has at least h vertices.The structure of the thesis is organized as follows.In Chapter 1,we introduce the background,terminology and notations and the main results of this thesis.In Chapter 2,once the lexicographic order is optimal for the edge isopermetric problem on the graphs including the the power graphs,we obtain an explicit solution by using the theory of number representation and ?(G)-sequence.As applications,this paper studies the h-extra edge-connectivity of parallel and distributed systems based on n-dimensional folded hypercube FQn,n-dimensional bijective connection networks Bn and 3-ary n-cubes Qn3.In chapter 3,the h-extra edge-connectivity of FQn ?h(FQn)is considered.As FQn contains 2n vertices,?h(FQn)is well-defined for each positive integer h?2n-1 = N/2.We study the following three cases:(1)determining the exact values of?h(FQn)and ?h-optimality for integer h,1 ?h?2(?)n/2(?)+1 and 6?n.(2)showing that ?h(FQn)is the constant((?)n/2(?)-r + 1)2(?)n/2(?)+r for 2(?)n/2(?)?r-lr ? h ? 2(?)n/2(?)+r,where r =1,2...,(?)n/2-1 and lT = 22T-1/3 if n is odd and lT= 22r+1-2/3 if n is even.(3)for each positive integer 1?h? 2n-1,designing an efficient O(log2(N))algorithm to totally determine the exact values and ?h-optimality of ?h(FQn).Our results improve several previous known results for h<n.In chapter 4,the h-extra edge-connectivity of Bn ?h(Bn)is investigated.We study the following two cases:finding a necessary and sufficient condition all for 1 ? h ? 2n-1,satisfying that ?h(Bn)=(n-c)2c,for c ? n-1;for each positive integer 1 ? h ? 2n-1,also designing an efficient O(log2(N))algorithm to totally determine the exact values and ?h-optimality of ?h(Bn).Our results improve the several previous known results for 1 ? h ?2(?)n/2(?)?1 and(?)2n-1/3(?)? h? 2n-1.In Chapter 5,for exponentially many values of h,1 ? h? 3(?)n/2(?),and h = 3c,0 ? c ? n-1,the exact values of ?h(Qn3)are given by an explicit expression and ?h-optimality is also determined.Our results improve the several previous known results for h<3.In Chapter 6,we shows that once this class of the n-dimensional bijective con-nection networks are embedded into a path,they share the minimum edge congestion(?)2n+1/3(?)and the minimum wirelength.22n-1-2n-1.The edges in the path with minimum edge congestion approximate a Cantor set.