Fault-hamiltonianity Of The Cartesian Product Graphs Of Paths And Cycles

With the rapid development of information science and the increasing amount of information and computation,people urgently need faster and higher performance computer systems.Parallel computer systems emerge as the times require.The realization of the function of the parallel computer system largely depends on the performance of the system interconnection network.With the continuous expansion of the scale of computer systems,the probability of failure of each component and component is increasing,so fault tolerance has become one of the key indicators to measure the performance of interconnection networks.It mainly considers whether the network can maintain some characteristics in the event of failure.The topology of interconnection networks is usually represented by graphs.The Cartesian product of graphs is one of the common methods to construct networks.The Cartesian product graph of paths and cycles,paths and paths,and cycles and cycles are common network topologies in parallel computer systems,which have good regularity and embeddability,and has received extensive attention.The existence of fault-tolerant Hamiltonian cycles and fault-tolerant Hamiltonian paths are classical problems in the research of interconnection networks.In this paper,we discuss the fault-tolerant Hamiltonian connectivity and Hamiltonianity of Cartesian product graphs Pm × Cn with path and cycle,Cn × Cn with two cycles,and Qnk with n cycles.Firstly,this paper studies the fault-tolerant Hamiltonian connectivity of the Cartesian product graph Pm × Cn of paths and cycles(where m≥ 3 and n≥ 5 are odd).According to the location of the fault edge,the fault-tolerant Hamiltonian path of Pm × Cn is characterized.The following conclusions are obtained:Conclusion 1:Let f be a fault edge in Pm × Cn,m≥3 is an integer and n≥ 5 is an odd integer.(1)If f is a column edge,Pm×Cn-f is Hamiltonian connected except that there is no Hamiltonian path from point v12 to point v1n.(2)If f is a row edge and f(?)R(1)∪R(m),then Pm×Cn-f is Hamiltonian connected.(3)If f is a row edge and f E R(1)∪ R(m),there exists a Hamiltonian path between any even point and other points in Pm × Cn-f.Secondly,this paper studies the edge Hamiltonian of the Cartesian product graph Cn×Cn of two cycles,and obtains the following results:Conclusion 2:In the Cartesian product graph Cn×Cn of two cycles(n≥5 is an odd number),f1 and f2 are two adjacent fault edges,then for any non-fault edge in Cn × Cn,there is a Hamiltonian cycle in Q2k-{f1,f2}containing this edge.Finally,the edge Hamiltonian of Cartesian product graphs of n cycles under conditional fault assumption is discussed,and the following results are obtained:Conclusion 3:Let F be the fault edge set of Cartesian product graph Qnk of n cycles,satisfying |F|≤4n-7 and δ(Qnk-F)≥2,then graph Qnk-F is edge Hamiltonian,where n≥2 and k≥5 is odd.