Hyper hamiltonian laceability on edge fault star graph

Abstract

The star graph posses many nice topological properties. Edge fault tolerance is an important issue for a network since the edges in the network may fail sometimes. In this paper, we show that the n-dimensional star graph is (n - 3)-edge fault tolerant hamiltonian laceable, (n - 3)-edge fault tolerant strongly hamiltonian laceable, and (n - 4)-edge fault tolerant hyper hamiltonian laceable. All these results are optimal in a sense described in this paper. (C) 2003 Elsevier Inc. All rights reserved.