The Restricted Edge-connectivity Of Order K Of Bubble-sort Graphs

An interconnection network is usually represented by an graph G=(V,E) and many large-scale multiprocessor systems take an interconnection network as underlying topologies. In a large-scale 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 large-scale 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,2-restricted edge connectivity is also called restricted edge connectivity which is denoted byλ'(G).The Bubble-sort 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≤n-1 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 edge-connectivity of Bubble-sort 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 edge-connectivity of Bubble-sort graphs. The main result is as follows.Let Bn be a Bubble-sort graph with n≥3 andλ'(Bn) be the restricted edge connec-tivity of Bn. Thenλ'(Bn)=2n-4.In Chapter 3, we study the 3-restricted edge-connectivity of Bubble-sort graphs. The main result is as follows.Let Bn be a Bubble-sort graph with n≥3 andλ{Bn) be the 3-restricted edge connectivity of Bn. Thenλ3(Bn)= 3n-7. In Chapter 4, we study the 4-restricted edge-connectivity of Bubble-sort graphs. The main result is as follows.Let Bn be a Bubble-sort graph with n≥4 andλ4(Bn) be the 4-restricted edge connectivity of Bn. Thenλ4{Bn)=4n-12.