The globally bi-3* and hyper bi-3* connectedness of the spider web networks

摘要

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)).