Article ID Journal Published Year Pages File Type
9506555 Applied Mathematics and Computation 2005 14 Pages PDF
Abstract
Assume that m and n are positive even integers with m ⩾ 4. The spider web network SW(m, n) is recognized as a variation of the honeycomb rectangular mesh HREM(m, n) [I. Stojmenovic, Honeycomb Networks: Topological Properties and Communication algorithms, IEEE Trans. Parallel and Distributed Systems 8 (1997) 1036-1042. [10]], and is a 3-regular bipartite planar graph. Suppose that SW(m, n) has bipartition V1 and V2. In this paper, we prove that for any x ∈ V1 and y ∈ V2, there exist three internally disjoint paths between x and y whose union spans SW(m, n). Moreover, for any three vertices x, y and z of the same partite set, there exist three internally disjoint paths between x and y whose union spans SW(m, n) − z. Such results imply that SW(m, n) remains hamiltonian when it contains a pair of faulty vertices of the opposite partite sets, or when it contains a faulty edge. More precisely, SW(m, n) − {x, y} is hamiltonian for any x ∈ V1 and y ∈ V2, and SW(m, n) − e is hamiltonian for any e ∈ E(SW(m, n)).
Related Topics
Physical Sciences and Engineering Mathematics Applied Mathematics
Authors
, ,