Hamiltonian cycles in hypercubes with more faulty edges

ABSTRACT

The hypercube $Q_n$ is one of the best known interconnection networks for parallel and distributed systems. In this paper we consider hamiltonian cycles in hypercubes $Q_n(n\ge 6)$ with faulty edges. It is proved that there still exists a fault-free hamiltonian cycle in the hypercube with 3n−7 faulty edges if the following two conditions are satisfied: (1) the degree of every vertex is at least two, (2) there do not exist a forbidden $f_4$-cycle or $f_6$-cycle. Our result is optimal in some sense.

KEYWORDS:

• Interconnection networks
• hypercubes
• fault-tolerant
• Hamiltonian cycles

2010 AMS SUBJECT CLASSIFICATIONS:

• C.2.1
• 97K30

Acknowledgments

We are much grateful to the anonymous referees for a number of helpful comments and suggestions that have improved the exposition of the paper.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work is supported by the National Natural Science Foundation of China [61303020, 61202017, 11402139] and the Program for the Outstanding Innovative Teams of Higher Learning Institutions of Shanxi.