Fault-tolerant Induced Diameter For The Interconnection Network

Consider a communication network G in which a limited number of edge (arc) and/or vertex faults F might occur. A routing p, i.e. a fixed path between each pair of vertices, for the network must be chosen without knowing which components might become faults. The diameter of the surviving route graph R(G, ρ)/F, where R(G,ρ)/F is a digraph with the same vertices as G-F and a vertex x being adjacent to another vertex y if and only if ρ(x,y) avoids F, the diameter of surviving route graph denoted by D(G,p), could be an important measurement for the routing p.This paper consists five chapters:The first Chapter describes the research background of graph theory and the concept of term; The second Chapter focus on Cartesian product of graph, it is well know that the Cartesian product method is an important method for designing large-scale communication network. The third Chapter describes fault-tolerant routing of networks and some conclution for fault-tolerant routing. The fourth Chapter describes the fault-tolerant routing in the Cartisian product graph, the author consider the Cartesian product digraphs whose factors satisfy some given conditions and show that the diameter of the surviving route graph is bounded by d(≥2) for any minimal routing when the number of faults is less than some integer. This result is also useful for the Cartesian product graphs and generalizes some known results.The final Chapter is a summary and outlook of this article.