Dissertation > Excellent graduate degree dissertation topics show

The Restricted Edge-connectivity and Restricted Arc-connectivity of Strong Product Graphs

Author: LiYang
Tutor: WangShiYing
School: Shanxi University
Course: Applied Mathematics
Keywords: Strong product graphs Restricted edge-connectivity Restricted Arc-connectivity Edge-connectivity Arc-connectivity Strongly connected
CLC: O157.5
Type: Master's thesis
Year: 2011
Downloads: 8
Quote: 0
Read: Download Dissertation

Abstract


The multiprocessor interconnection networks are conveniently modeled by graphs or digraphs, in which the vertex corresponds to processor and the edge (arc) corresponds to communication link. One fundamental consideration in the design of such networks is the reliability, which can usually be measured by the edge-connectivity (arc-connectivity) of the graph (digraph). The larger the edge-connectivity (arc-connectivity) is, the more reliable the network is. Besides the edge-connectivity, the restricted edge-connectivity has been broadly concerned recently. The article is divided into three chapters, in which, the restricted edge-connectivity of strong product graphs and the restricted arc-connectivity of strong product digraphs are studied.In Chapter 1, we give some basic notations and terminologies on graphs.In Chapter 2, we introduce the concept of strong product graphs and give a upper bound and a lower bound of the restricted edge-connectivity of strong product graphs and some corollaries.(1) Let G1 and G1 be two connected graphs with connectivityλ1 andλ2, respectively. Then(2) Let G be a connected graph with connectivityλand |V(G)|>2. Thenλ’(K2(?) G)=4A.(3)Let G1 and G1 be two connected graphs with connectivityλ1 andλ2, respectively. Then(4)If G1 and G1 are two maximally edge-connected graphs andσ≥2,σ2≥2, then G1(?)G2 is super edge-connected.(5)Let D=Cm(?)Cn and m, n≥3. Thenλ’(D)=14.In Chapter 3, we study the restricted arc-connectivity of a class of strong product digraphs. The main results are as follows:(1) Let Di(i=1,2) be a nontrivial strongly connected digraph with order ni and arc-connectivityλi and let D=D1(?)D2. Then(2) Let D1 be a nontrivial strongly connected digraph such that|V(D1)|＞2 and letσandλbe the minimum degree and arc-connectivity, respectively. Ifσ+=σ-=σ, thenλ’(C2(?)D1)=4A.

Related Dissertations

  1. Restricted Connectivity of Line Digraphs and Cartesian Product Digrphs,O157.5
  2. Figure certain basic parameters of,O157.5
  3. Petri net -based workflow process model verification and performance evaluation method of,TP301.1
  4. Edge-Connectivity of Graphs and Digraphs,O157.5
  5. Domination Number and Restricted Edge Connectivity of Product Graphs,O157.5
  6. The High Order Restricted Edge-connectivity of Graphs,O157.5
  7. The Generalized Exponents of Primitive Nearly Reducible Matrices,O151.21
  8. Connectedness of Bi-Cayley Graphs and Bi-Transitive Graphs,O157.5
  9. Higher Order Connectedness of Graphs and Digraphs,O157.5
  10. Connectedness and Domination of Several Kinds of Graphs,O157.5
  11. Two tournaments in the study circle,O157.5
  12. On Optimal Problem of 3-restricted Edge Connectivity in Graghs,O157.5
  13. The Crossing Number of Some Results,O157.5
  14. Problem of Componentwise Complementary Cycles in 2-Equilibrium Multipartite Tournaments,O157.5
  15. Study parameters on network stability,O157.5
  16. The Study on Fault Tolerance of Several Interconnection Networks,TN915.02
  17. The Length of Limit Cycles For Fuzzy Bidirectional Associative Memories and Algorithms to Compute the Period Index of Fuzzy Matrix,O159
  18. Some Problems of the Connectivity of Graph,O157.5
  19. On Super Restricted Edge Connectivity and Lower Bounds on the Edge-Connectivity of Graphs,O157.5
  20. Primitive almost around the matrix on the k- index,O157.5
  21. Strong product graphs dictionary product graph restricted edge connectivity,O157.5

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