Title :
Conditional Fault-Tolerant Cycle Embedding of Star Graphs
Author :
Yang, Ming-Chien
Author_Institution :
Dept. of Knowledge Manage., Aletheia Univ., Tainan, Taiwan
Abstract :
The star graph has been an attractive interconnection network, and possesses many nice properties. In this paper, we consider the cycle embedding problem in star graphs with conditional edge faults. We show that there exist cycles of all even lengths from 6 to n! in an n-dimensional star graph with ¿ 2n - 7 edge faults in which each vertex is incident with at least two healthy edges for n ¿ 4.
Keywords :
network theory (graphs); conditional edge fault; conditional fault-tolerant cycle embedding; interconnection network; star graph; Computer networks; Data structures; Distributed computing; Fault tolerance; Knowledge management; Multicast algorithms; Multiprocessor interconnection networks; Parallel algorithms; Routing; Tin; embedding; hamiltonian; interconnection networks; pancyclic; star graph;
Conference_Titel :
Parallel and Distributed Computing, Applications and Technologies, 2009 International Conference on
Conference_Location :
Higashi Hiroshima
Print_ISBN :
978-0-7695-3914-0
DOI :
10.1109/PDCAT.2009.29
