The Cycles And Paths In Hypercube And Honeycomb Rectangular Torus

Graph embedding problem is one of the central issues in evaluating an interconnection network,and the important benifit of this problem is that we can apply existing algorithms for guest graphs to host graphs.Rings and linear arrays are two fundamental networks in parallel processing and distributed computing due to thief low-cost communication.A network having Hamiltonian cycle or Hamiltonian path can efficiently simulate many algorithms designed on rings and linear arrays,so it is basic to have effective cycle or path embedding in designing network topologies. The link or node failures are inevitable when a large system is put in use,therefore, fault-tolerent ability of an interconnection network is a critical issue in parallel computing.It is practical and important to research a system with failures.The hypercube and honeycomb rectangular torus are two common interconnection networks,n-dimensional hypercube(denoted by Q_n) is an n-regular bipartite graph with 2~n.A honeycomb rectangular torus(denoted by HReT(m,n)) is a 3-regular graphs,it is obtained from the torus(a network topology,that is,the Cartesian product of two circles) by deleting its some edges.Due to their many good topological properties,they have been used in parallel processing and distributed computing systems.In this paper,the following two problems are considered:1.Fault-free cycles passing through a prescribed linear forest(a subgraph in which every component is a path) in a hypercube with faulty edges;and 2.Hamiltonian cycle and Hamiltonianlaceability in a honeycomb rectangular torus.Some results are obtained on the following:1.Fycles passing through the prescribed a linear forest of three edges in a hypercube;2.Fault-free cycles passing through the prescribed a linear forest in a hypercube with faulty edges;3.Fault-free hamiltonian cycle in a honeycomb rectangular torus with faulty edges;and4.Strong Hamiltonian-laceability in a honeycomb rectangular torus.