Graph Theoretical Studies On Reliability Of Networks And Minimum Broadcast Graphs

Due to widespread use of (and demand for) reliable, efficient, and fault-tolerant networks, network topology has been extensively studied over the past two decades. Since the topology of a network is usually modeled by a graph, graph theory can be usefully applied in many ways to networks design and analysis. This thesis investigates reliability of networks, which is an important criterion in the design of interconnection networks, by means of some indices of graph theory such as wide-diameter, (d, m)-dominating number, super edge-connectivity and restricted edge-connectivity, and we have:1. Two unidirectional n-dimensional hypercubes, namely, Q₁(n) and Q₂(n), proposed as high-speed networking schemes by Chou and Du, are researched (see [11]). We show that the smallest possible length for any maximum fault-tolerant container from a to b is at most n + 2 whether a and b are in Q₁(n) or in Q₂(n). Furthermore,we prove that the wide-diameters of Q₁(n) and Q₂(n) are equal to n+2. At last, we show the conjecture in [29] is true.2 The (d, m)-dominating number of the m-dimensional hypercube Q_m (m ≥ 4) is 2 for any integer d. ([m/2] + 2 ≤ d ≤ m).3. (i) For the n-dimensional undirected binary de Bruijn graphs, UB(2,n), n ≥ 4, there is a vertex x = x₁(x|ˉ)₁(x|ˉ)₁ … (x|ˉ)₁x₁ (x₁ = 1 or 0) such that for any other vertex t there exist at least two internally disjoint paths of length at most n - 1 between x and t in U B(2,n), i. e., the (n — 1,2)-dominating number of U B(2,n) is equal to one.(ii) For n ≥ 5, let S = {100 … 01, 011 … 10}. For any other vertex t there exist at least two internally disjoint paths of length at most n - 2 between t and S in U B(2,n), i. e., the (n — 2, 2)-dominating number of U B(2,n) is no more than 2.4. The (d, 2n)-dominating number of the toroidal mesh C(d₁, d₂ …, d_n) is 2 ford = diam(C(dud2, ? â–  â–  ,dn)) when n > 3 and d, > 3 for i € {], 2, ? ? ?, n}.5. The undirected de Bruijn graphs UB{d, n) is super-A (d > 2, n > 2) and the restricted edge connectivity of UB(2,n) is 4 when n > 3; but it is 3 for n = 3.Another problem — minimum broadcast graphs, which has been studied by many scholars over the past two decades, is also investigated in this thesis. It is well known that the minimum broadcast graphs are difficult to construct and there is no known method for constructing a minimum broadcast graph for arbitrary n. Since people construct a broadcast graph with large order by means of constructing several broadcast graphs with smaller order in general, the minimum broadcast graphs with small order are important and the value of B{n) for n < 22 have been determined. Thus, the value of jB(23) is the first number unable to be determined. In this thesis, we show:6. ï¿¡(23) is 33 or 34, i.e., the minimum broadcast graphs of 23 vertices have 33 or 34 edges.