Ring embedding in faulty generalized honeycomb torus – GHT(m, n, n/2)

Abstract

The honeycomb torus HT(m) is an attractive architecture for distributed processing applications. For analysing its performance, a symmetric generalized honeycomb torus, GHT(m, n, n/2), with m≥2 and even n≥4, where m+n/2 is even, which is a 3-regular, Hamiltonian bipartite graph, is operated as a platform for combinatorial studies. More specifically, GHT(m, n, n/2) includes GHT(m, 6m, 3m), the isomorphism of the honeycomb torus HT(m). It has been proven that any GHT(m, n, n/2)−e is Hamiltonian for any edge e∈E(GHT(m, n, n/2)). Moreover, any GHT(m, n, n/2)−F is Hamiltonian for any F={u, v} with u∈B and v∈W, where B and W are the bipartition of V(GHT(m, n, n/2)) if and only if n≥6 or m=2, n≥4.

Keywords:

• fault-tolerance
• generalized honeycomb torus
• graph embedding
• Hamiltonian cycle
• interconnection networks

2000 AMS Subject Classifications :

• 05C60
• 68M10
• 68R10
• 68M15
• 94C15

Acknowledgements

The authors are very grateful to the anonymous referees for their thorough review of the paper and for their concrete, helpful suggestions. This work was partially supported by the National Science Council of the Republic of China under the contract NSC 93-2211-E-157-003.