Dissertation > Excellent graduate degree dissertation topics show

The Restricted Edge-connectivity of Order k of Bubble-sort Graphs

Author: ChenYuJuan
Tutor: WangShiYing
School: Shanxi University
Course: Applied Mathematics
Keywords: Interconnection networks k-Restricted edge cut k-Restricted edge connectivity Bubble-sort graphs
CLC: O157.5
Type: Master's thesis
Year: 2011
Downloads: 11
Quote: 0
Read: Download Dissertation

Abstract


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.

Related Dissertations

  1. The Restricted Edge-connectivity and Restricted Arc-connectivity of Strong Product Graphs,O157.5
  2. Domination Number and Restricted Edge Connectivity of Product Graphs,O157.5
  3. The High Order Restricted Edge-connectivity of Graphs,O157.5
  4. Higher Order Connectedness of Graphs and Digraphs,O157.5
  5. On Optimal Problem of 3-restricted Edge Connectivity in Graghs,O157.5
  6. Based load balancing hypercube network fault tolerant routing algorithm,TP393.02
  7. Connectivity of the network structure and completely positive matrices,O157.5
  8. The Study on Fault Tolerance of Several Interconnection Networks,TN915.02
  9. On Super Restricted Edge Connectivity and Lower Bounds on the Edge-Connectivity of Graphs,O157.5
  10. 3-Restricted Edge Connectivity and 3-Restricted Connectivity of Graphs,O157.5
  11. λ_k-Optimality of Complete Bipartite Graphs and Harary Graphs,O157.5
  12. Strong product graphs dictionary product graph restricted edge connectivity,O157.5
  13. Restricted Edge Connectivity of Cartesian Product and Direct Product Graphs,O157.5
  14. On Conditional Edge Connectedness of Transitive Graphs,O157.5
  15. Higher Order Connectedness of a Graph,O157.5
  16. k- restricted edge connectivity existence and upper bound,O157.5
  17. Sufficient Conditions for k-Restricted Edge Connectivity to Be λ_k-Optimal and Super-λ_k in Graphs,O157.5
  18. Optimality and Superiority of k-Restricted Edge Connectivity of Graphs,O157.5
  19. Figure on the k- restricted edge connectivity properties of,O157.5
  20. The Path and Geodesic Pancyclic Embedding in the Hypercubes and k-ary N-cubes with Faulty Edges,O157.5
  21. The Lower-order Restricted Edge-connectivity of Graphs,O157.5

CLC: > Mathematical sciences and chemical > Mathematics > Algebra,number theory, portfolio theory > Combinatorics ( combinatorics ) > Graph Theory
© 2012 www.DissertationTopic.Net  Mobile