Fault Hamiltonicity and fault Hamiltonian-connectivity of generalised matching networks

Abstract

Generalised matching network (GMN) is a newly introduced kind of interconnection network, which generalises hypercube-like network. This paper addresses the fault Hamiltonicity and fault Hamiltonian-connectivity of GMNs. Let G be a GMN with at least four building graphs, each of which is f-fault Hamiltonian-connected and -fault Hamiltonian. We prove that if G satisfies two more specified assumptions, then G is -fault Hamiltonian-connected and -fault Hamiltonian.

Keywords:

• interconnection networks
• generalised matching network
• Hamiltonicity
• Hamiltonian-connectivity
• fault-tolerance

Acknowledgements

We would like to express our gratitude to the three anonymous referees for their valuable suggestions that greatly improve the quality of the paper. This work is supported by Natural Science Foundation of China (10771227), Program for New Century Excellent Talent of Educational Ministry of China (NCET-05-0759), Doctorate Foundation of Educational Ministry of China (20050611001), Natural Science Foundation of Chongqing CSTC (2006BB2231), and Chongqing University Postgraduates' Science and Innovation Fund (200701Y1A0050191).