Spider web networks: a family of optimal, fault tolerant, hamiltoman bipartite graphs

Abstract

In this paper, we propose a honeycomb mesh variation, called a spider web network. Assume that in and it are positive even integers with m greater than or equal to 4. A spider web network SW(m, n) is a 3-regular bipartite planar graph with bipartition C and D. We prove that the honeycomb rectangular mesh HREM(m, n) is a spanning subgraph of SW(m, n). We also prove that SW(m, n) - e is harniltonian for any e is an element of E and SW(m, n) - {c, d} remains hamiltonian for any c is an element of C and d is an element of D. These hamiltonian propel-ties are optimal. (C) 2003 Elsevier Inc. All rights reserved.