Title :
Conditional Fault-Tolerant Hamiltonicity of Star Graphs
Author_Institution :
Dept. of Electron. Eng., Nat. United Univ., Miaoli
Abstract :
The star graph possesses many nice topological properties. In this study, we show that for any n dimensional star graph (n ges 4) with les 2n - 7 edge faults in which each node is incident to at least two non-faulty edges, there exists a fault-free Hamiltonian cycle. Compare with the corresponding study in hypercube, our method is rather succinct
Keywords :
fault tolerance; graph theory; multiprocessor interconnection networks; fault-tolerant Hamiltonicity; star graphs; topological property; Algorithm design and analysis; Broadcasting; Computer networks; Concurrent computing; Distributed computing; Fault tolerance; Hypercubes; Network topology; Routing; Tin;
Conference_Titel :
Parallel and Distributed Computing, Applications and Technologies, 2006. PDCAT '06. Seventh International Conference on
Conference_Location :
Taipei
Print_ISBN :
0-7695-2736-1
DOI :
10.1109/PDCAT.2006.45
