Fault-tolerant Parameters Of Graphs

The interconnection network of a multiprocessor system is often modeled by a (di) graph. Therefore, the performance of networks can be measured by the proper-ties and parameters of (di) graphs. One fundamental consideration is the fault toler-ance in designing or selecting the network for a system. A multiprocessor system is said to be fault-tolerant if the network of the system remains connected or contains some topological structure in the presence of failures. Therefore, the fault toler-ance of networks can be measured by the fault-tolerant parameters of (di) graphs on connectivity or some topological structure. The investigation on such fault-tolerant parameters of (di) graphs is full of theoretical significance and application value.The thesis consists of four chapters. In Chapter 1, after a brief introduction to the contents and significance of this work and the used basic notation and termi-nology, we give a survey on research advance of the related works and list our main results.The edge connectivity is one classical parameter to measure the level of connect-edness of graphs. The κ-restricted edge connectivity was proposed by generalizing the edge connectivity. Furthermore, the super κ-restricted edge connectivity (super-λκ property) was proposed, where the super 1-restricted edge connectivity and super 2-restricted edge connectivity are also known as the super edge connectivity (super-λ property) and super restricted edge connectivity (super-λ’property), respectively. In 2012, Hong et al. proposed the edge fault tolerance Sλ(G) of a graph G on the super-λ property. The parameter Sλ(G) can be used to evaluate the fault tolerance of networks. In Chapter 2, we investigate two fault-tolerant parameters of graphs. First, the edge fault tolerance Sλκ(G) of a graph G on the super-Aλκ property is presented, which is a generalization of Sλ(G) proposed by Hong et al. We define a super-λκ graph G to be m-super-λκ if G - S is still super-λκ for any edge set S with |S|≤ m. The maximum integer of such m, denoted by Sλκ(G), is said to be the edge fault tolerance of G on the super-λκ, property, where Sλκ(G) is also denoted by Sλ’(G). Next we give the lower and upper bounds on Sλ’(G) for the general graphs. An example shows that the lower and upper bounds are best possible. More refined bounds on Sλ’(G) are obtained for regular graphs, semi-regular graphs, edge tran-sitive graphs and the cartesian product of graphs. In particular, the exact values of Sλ’ (G) are obtained for some special classes of graphs. Finally, we give the lower and upper bounds on Sλ3 (G) for the general regular graphs and determine the exact value of Sλ3(G) for a special class of regular graphs. More refined bounds on Sλ3(G) are obtained for the cartesian product of regular graphs and an example shows that the obtained bounds are best possible.The super arc connectivity (super-A property) and super restricted arc connec-tivity (super-λ’property) were proposed by generalizing the super edge connectivity and super restricted edge connectivity to digraphs. In Chapter 3, we investigate two fault-tolerant parameters of digraphs. First, the arc fault tolerance Sλ(D) (resp. Sλ’(D)) of a digraph D on the super-A property (resp. super-λ’property) is pre-sented, which is a generalization of Sλ(G) proposed by Hong et al. to digraphs. We define a super-λ digraph D to be m-super-λ if D - S is still super-λ for any arc set S with |S|≤m. The maximum integer of such m, denoted by Sλ(D), is said to be the arc fault tolerance of D on the super-λ property. Similarly, we can define Sy(D). Next we provide a necessary and sufficient condition for the cartesian product of digraphs (resp. the cartesian product of regular digraphs) D to be super-A (resp. super-λ’). Finally, we give the lower and upper bounds on Sλ(D) and Sλ(D). The examples show that the lower and upper bounds are best possible. In particular, the exact values of Sλ(D) and Sλ(D) are obtained in some special cases.Becker and Simon proposed the fault-tolerant parameter of the n-dimensional hypercube on the (n-κ)-dimensional subcube in 1986. The k-ary n-cube is a gener-alization of the n-dimensional hypercube and is one of the most popular networks in large-scale multiprocessor systems. In Chapter 4, we investigate two fault-tolerant parameters f(n, m) and f*(n, m) of the κ-ary n-cube on the k-ary (n-m)-subcube, where f(n,m) (resp. f*(n,m)) is the minimum number of vertices (resp. vertices and edges) whose removal makes every κ-ary (n - m)-cube damaged in the κ-ary n-cube. We present the lower and upper bounds on f(n,m) and f*(n,m), and determine the exact values of the two parameters for some special m’s.