### Abstract

Two Hamiltonian paths are said to be fully independent if the ith vertices of both paths are distinct for all i between 1 and n, where n is the number of vertices of the given graph. Hamiltonian paths in a set are said to be mutually fully independent if two arbitrary Hamiltonian paths in the set are fully independent. On the other hand, two Hamiltonian cycles are independent starting at v if both cycles start at a common vertex v and the ith vertices of both cycles are distinct for all i between 2 and n. Hamiltonian cycles in a set are said to be mutually independent starting at v if any two different cycles in the set are independent starting at v. The n-dimensional hypercube is widely used as the architecture for parallel machines. In this paper, we study its fault-tolerant property and show that an n-dimensional hypercube with at most n-2 faulty edges can embed a set of fault-free mutually fully independent Hamiltonian paths between two adjacent vertices, and can embed a set of fault-free mutually independent Hamiltonian cycles starting at a given vertex. The number of tolerable faulty edges is optimal with respect to a worst case.

Original language | English |
---|---|

Pages (from-to) | 153-162 |

Number of pages | 10 |

Journal | Journal of Combinatorial Optimization |

Volume | 13 |

Issue number | 2 |

DOIs | |

Publication status | Published - 2007 Feb 1 |

### All Science Journal Classification (ASJC) codes

- Computer Science Applications
- Discrete Mathematics and Combinatorics
- Control and Optimization
- Computational Theory and Mathematics
- Applied Mathematics