Tsai, Ping-YingPing-YingTsaiFu, Jung-ShengJung-ShengFuChen, Gen-HueyGen-HueyChen2009-04-292018-07-052009-04-292018-07-052009https://www.scopus.com/inward/record.uri?eid=2-s2.0-59049098382&doi=10.1016%2fj.tcs.2008.11.012&partnerID=40&md5=6cf19cf7f25a20fc83e59c5d3c15dec9The star network, which belongs to the class of Cayley graphs, is one of the most versatile interconnection networks for parallel and distributed computing. In this paper, adopting the conditional fault model in which each node is assumed to be incident with two or more fault-free links, we show that an n-dimensional star network can tolerate up to 2 n - 7 link faults, and be strongly (fault-free) Hamiltonian laceable, where n ≥ 4. In other words, we can embed a fault-free linear array of length n ! - 1 (n ! - 2) in an n-dimensional star network with up to 2 n - 7 link faults, if the two end nodes belong to different partite sets (the same partite set). The result is optimal with respect to the number of link faults tolerated. It is already known that under the random fault model, an n-dimensional star network can tolerate up to n - 3 faulty links and be strongly Hamiltonian laceable, for n ≥ 3. © 2008 Elsevier B.V. All rights reserved.application/pdf1365727 bytesapplication/pdfen-USConditional fault model; Embedding; Fault tolerance; Hamiltonian laceability; Random fault model; Star networkjournal article10.1016/j.tcs.2008.11.0122-s2.0-59049098382http://ntur.lib.ntu.edu.tw/bitstream/246246/154735/1/51.pdf