Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9506555 | Applied Mathematics and Computation | 2005 | 14 Pages |
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
Shin-Shin Kao, Lih-Hsing Hsu,