Strong Reliability of Star Graphs Interconnection Networks

Limei Lin, Yanze Huang, Sun Yuan Hsieh, Li Xu

Research output: Contribution to journalArticlepeer-review

Abstract

For interconnection network losing processors, it is considerable to calculate the number of vertices in the maximal component in the surviving network. Moreover, the component connectivity is a significant indicator for reliability of a network in the presence of failing processors. In this article, we first prove that when a set <formula><tex>$M$</tex></formula> of at most <formula><tex>$3n-7$</tex></formula> processors is deleted from an <formula><tex>$n$</tex></formula>-star graph, the surviving graph has a large component of size greater or equal to <formula><tex>$n!-|M|-3$</tex></formula>. We then prove that when a set <formula><tex>$M$</tex></formula> of at most <formula><tex>$4n-9$</tex></formula> processors is deleted from an <formula><tex>$n$</tex></formula>-star graph, the surviving graph has a large component of size greater or equal to <formula><tex>$n!-|M|-5$</tex></formula>. Finally, we also calculate the <formula><tex>$r$</tex></formula>-component connectivity of the <formula><tex>$n$</tex></formula>-star graph for <formula><tex>$2\leq r\leq 5$</tex></formula>.

Original languageEnglish
JournalIEEE Transactions on Reliability
DOIs
Publication statusAccepted/In press - 2020

All Science Journal Classification (ASJC) codes

  • Safety, Risk, Reliability and Quality
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Strong Reliability of Star Graphs Interconnection Networks'. Together they form a unique fingerprint.

Cite this