Fault-tolerant Bipancyclicity Of Two Kinds Of Networks

A multicomputer system is comprised of multiple processors that communicate by exchanging messages through an interconnection network.These processors work together in order to solve large application problems.Basically,each node has a communication module.The topological structure of a network is usually modeled by a simple,connected,undirected graph.It is well known that hypercubes and star graphs are two of the most versatile and efficient architecture yet discovered for building massively parallel systems.They are attractive interconnection networks,and possess many nice properties,such as recursiveness,regularity,symmetry,maximal fault-tolerance,vertex transitivity,edge transitivity and strong resilience,which are very important for designing massively parallel systems.Fault tolerance is an important property of an interconnection network because vertex faults and edge faults may occur on it.The pancyclicity(or bipancyclicity for bipartite networks)is an important measurement to determine whether a network is suitable for an application mapping rings of any length into the network.We consider the fault-tolerant bipancyclicity of hypercubes and star graphs in this thesis.Letf_e(respectively,f_v)denote the number of faulty edges(respectively,vertices)in an n-dimensional hypercubeQ_n.For the first main result of this thesis,by building on earlier studies and research regarding a topic,we prove that iff_e?2n-5,f_v(10)f_e?2n-4and every fault-free vertex is incident with at least two fault-free edges,thenQ_n(7)n?5(8)contains a fault-free cycle of every even length from 4 to2~n-2f_v.For star graphs,we letf_e(respectively,f_v)denote the number of faulty edges(respectively,vertices)in an n-dimensional star graphS_n.For the other main result,as an improvement of the results by prior research regarding this topic,we prove that if f_v(10)f_e?2n-7and every fault-free vertex is incident with or adjacent to at least two fault-free elements,thenS_n(7)n?4(8)contains a fault-free cycle of every even length from 6ton!-2f_v.