Fault-free mutually independent Hamiltonian cycles of faulty star graphs

Abstract

The star graph interconnection network has been recognized as an attractive alternative to the hypercube for its nice topological properties. Unlike previous research concerning the issue of embedding exactly one Hamiltonian cycle into an injured star network, this paper addresses the maximum number of fault-free mutually independent Hamiltonian cycles in the faulty star network. To be precise, let SG _n denote an n-dimensional star network in which f≤n−3 edges may fail accidentally. We show that there exist (n−2−f)-mutually independent Hamiltonian cycles rooted at any vertex in SG _n if n∈{3, 4}, and there exist (n−1−f)-mutually independent Hamiltonian cycles rooted at any vertex in SG _n if n≥5.

Keywords:

• Hamiltonian
• interconnection network
• star graph
• fault tolerance

2000 AMS Subject Classifications :

• 05C38
• 05C45
• 05C75
• 05C90
• 68M10

Acknowledgements

The authors express the most immense gratitude to Editor-in-Chief, Editor, and the anonymous referees for their careful reading and constructive comments. They greatly improve the quality of the paper. This work was supported in part by the National Science Council of the Republic of China under Contract NSC 98-2218-E-468-001-MY3. J.J.M. Tan was supported in part by the National Science Council of the Republic of China under Contract NSC 96-2221-E-009-134-MY3 and in part by the Aiming for the Top University and Elite Research Center Development Plan.