Fault Diameter Of Some Special Strong Product Graphs

With the development of parallel computing networks and supercomputers,high reliability and efficiency of interconnection networks are required.The fault diameter represents the maximum transmission delay of the network under the worst fault condition,and is an important parameter to measure the reliability and efficiency of the network.Strong product is an efficient graph product method for constructing large graphs from small graphs,and the constructed strong product graphs retain the ideal properties of many factor graphs.In order to design new interconnection network topologies with high reliability and efficiency,as well as expand the research scope of fault diameter of product graphs,research on the fault diameter of strong product graphs is carried out.Therefore,this thesis studies the fault diameter of several special strong product graphs with four basic graphs as factor graphs,namely,path,cycle,star graph and complete graph,there uses new methods to construct internally vertex or edge disjoint paths and the worst fault path to draw conclusions.Firstly,since the internally vertex disjoint paths are constructed based on the topologies of path,the vertex fault diameter of the strong product graph of two paths is determined.Then,according to the parity of the order of the factor graph and the topological structure characteristics of the strong product graph,the intersection paths between two vertices are defined.Based on this,the edge disjoint paths are constructed,and the edge fault diameter of the strong product graph of two paths is determined.According to the parity of cycle length and the topological structure of cycle,internally vertex disjoint paths are constructed based on inductive assumptions.Due to the centrality of the star graph,which means that the center vertex is adjacent to other remaining vertices,the internally vertex or edge disjoint paths between any two vertices are constructed based on this property,and the vertex fault diameter and edge fault diameter of the strong product graph of path and star graph are determined.Since connected graph can be divided into complete graph and incomplete connected graph,according to that the strong product graph of complete graph and complete graph is still complete graph,the vertex fault diameter of the strong product graph of complete graph and complete graph is directly obtained.Different from the conventional method of constructing the worst fault path through the fault-free neighbor vertex of the target vertex,this thesis gives the worst fault path by constructing isomorphic subgraphs containing the target vertex,thus determining the vertex fault diameter of the strong product graph of the incomplete connected graph and the complete graph,which can be expressed by the vertex fault diameter of the incomplete connected graph.