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

摘要

In this paper, we propose a honeycomb mesh variation, called a spider web network. Assume that m and n are positive even integers with m⩾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 hamiltonian for any e∈E and SW(m,n)−{c,d} remains hamiltonian for any c∈C and d∈D. These hamiltonian properties are optimal.