Hamiltionian laceability on the edge fault star graph

Abstract

The star graph is an attractive alternativeto the hypercube graph. It possess many nice toplolgical properties. Edge fault tolerance is an important isse for a network since the edges in the network may fail sometimes. In this paper, we show that then-dimensional star graph is (n-３)-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.