Fault-free mutually independent Hamiltonian cycles of faulty star graphs

Jiann-Mean Tan, Tzu-Liang Kung, Cheng-Kuan Lin, Tyne Liang, Lih-Hsing Hsu

Research output: Contribution to journalArticle

4 Scopus citations

Abstract

The star graph interconnection network has been recognized as an attractive alternative to the hypercube for its nice topological properties. Unlike previous research concerning the issue of embedding exactly one Hamiltonian cycle into an injured star network, this paper addresses the maximum number of fault-free mutually independent Hamiltonian cycles in the faulty star network. To be precise, let SG(n) denote an n-dimensional star network in which f <= n - 3 edges may fail accidentally. We show that there exist (n - 2 - f)-mutually independent Hamiltonian cycles rooted at any vertex in SGn if n epsilon {3, 4}, and there exist (n - 1 - f)-mutually independent Hamiltonian cycles rooted at any vertex in SG(n) if n >= 5.
Original languageEnglish
Pages (from-to)731-746
Number of pages16
JournalInternational Journal of Computer Mathematics
Volume88
Issue number4
DOIs
StatePublished - 2011

Keywords

  • Hamiltonian; interconnection network; star graph; fault tolerance

Fingerprint Dive into the research topics of 'Fault-free mutually independent Hamiltonian cycles of faulty star graphs'. Together they form a unique fingerprint.

  • Cite this