Hamiltonian laceability on edge fault star graph
Tseng-Kuei Li, J. Tan · 2003
The star graph is an attractive alternative to the hypercube graph. It possess 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.