The Restricted Edgeconnectivity of Order k of Bubblesort Graphs 

Author  ChenYuJuan 
Tutor  WangShiYing 
School  Shanxi University 
Course  Applied Mathematics 
Keywords  Interconnection networks kRestricted edge cut kRestricted edge connectivity Bubblesort graphs 
CLC  O157.5 
Type  Master's thesis 
Year  2011 
Downloads  11 
Quotes  0 
An interconnection network is usually represented by an graph G=(V,E) and many largescale multiprocessor systems take an interconnection network as underlying topologies. In a largescale multiprocessor system, failures of components are inevitable. Thus, fault tolerance of an interconnection network has become an important issue and has been extensively studied. Edge connectivity is an important parameter to measure the fault tolerance of an interconnection network and it is the worse case measure. However, the probability that all the edges related to some vertex are failure at the same time is very small in a real largescale multiprocessor system. Thus, Fabrega and Foil proposed the concept ofκrestricted edge connectivity to measure the reliability of a interconnection network. Theκrestricted edge connectivity of a graph G is the minimum cardinality of a set of edges, if any, whose deletion disconnects G and every remaining component has at least k vertices. In particularly,2restricted edge connectivity is also called restricted edge connectivity which is denoted byλ’(G).The Bubblesort graph, denoted by Bn, is an attractive interconnection network with some good topological properties such as highly symmetry and recursive structure for parallel and distributed systems. Bn, n≥1, is an undirected graph consisting of n! vertices each of which has the form of x=x1x2…xn, where 1≤Xi≤n and xi≠xi for distinct 1≤i, j≤n. Two vertices x=x1x2…xn and y= y1y2…yn are adjacent if and only if there exists an integer 1≤i≤n1 such that xi=yi+1, xi+1=yi and xi=yi for every j∈{1,2,…, n}\{i,i+1}.In this paper,we study theκrestricted edgeconnectivity of Bubblesort graphs where k∈{2,3,4}. The article contains four chapters.In Chapter 1, we introduce some preliminaries.In Chapter 2, we study the restricted edgeconnectivity of Bubblesort graphs. The main result is as follows.Let Bn be a Bubblesort graph with n≥3 andλ’(Bn) be the restricted edge connectivity of Bn. Thenλ’(Bn)=2n4.In Chapter 3, we study the 3restricted edgeconnectivity of Bubblesort graphs. The main result is as follows.Let Bn be a Bubblesort graph with n≥3 andλ{Bn) be the 3restricted edge connectivity of Bn. Thenλ3(Bn)= 3n7. In Chapter 4, we study the 4restricted edgeconnectivity of Bubblesort graphs. The main result is as follows.Let Bn be a Bubblesort graph with n≥4 andλ4(Bn) be the 4restricted edge connectivity of Bn. Thenλ4{Bn)=4n12.