Analysis Of Reliability On Alternating Group Graphs

As the Cayley graph based on alternating group An in group theory, alternating group graph AGn can be used as an interconnection network topology for multiprocessor systems. This family of graphs have been shown to have many nice properties including vertex-transitivity, edge transitivity, maximal vertex (edge) connectivity, and have smaller diameter and average distance. Moreover, alternating group graphs have many advantages over the families of hypercubes and star graphs, for example, they are not only vertex-(or edge-)fault hamiltonian-connected and pancyclic but also are panconnected. This paper takes alternating group graph AGn as subject investigated, and studies their fault tolerance, fault diagnosability, subgraph reliability analysis.The first chapter prepares some basic knowledge of the paper. It mainly introduces basis conceptions and notions of graph theory and combinatorial network theory, the development on connectivity and system level diagnosis models as well as background.The second chapter presents the fault tolerant analysis of alternating group graph AGn-Fault tolerant analysis is an important topic of interconnection networks studied today. Extra-connectivity has been proposed as an important parameter to estimate the fault tolerance of interconnection networks. This chapter presents characterization of fault tolerance on alternating group graph AGn, which lays a foundation for diagnosability. In detail, this chapter studies extra-connectivity of alternating group graph AGn, and establishes that K(1)o (AGn)=4n-11, K(2)o(AGn)=6n-19, K(3)o(AGn)=8n-28, respectively.The third chapter mainly focuses on conditional diagnosability of alternating group graph AGn under PMC model. Processor fault diagnosis is the foundation of fault-tolerant technology when processor failures arise but the running system is not allowed to interrupted. Besides, fault diagnosability plays an extremely important role on measuring the raliability of a multiprocessor system. The conditional diagnosability has been widely accepted as a practical metric parameter of diagnosability. This chapter determines that the conditional diagnosability of an n-dimensional alternating group graph AGn under the classical PMC diagnostic model is8n-27, which is about four times of its classic diagnosability.The forth chapter gives (n-1)-subgraph reliability in alternating group graph AGn under the probability fault model. The probabilistic reliability of the network is an valid strategy to evaluate network performance. Through the fixed dimension partitioning technique, the approximate (n-1)-altcrnating group graph reliability is obtained. Finally, Chapter five gives concluding remarks and outlines some possible future work in this area.