Strong Reliability of Star Graphs Interconnection Networks

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

doi:10.1109/TR.2020.3013158

Strong Reliability of Star Graphs Interconnection Networks

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

Department of Computer Science and Information Engineering

Research output: Contribution to journal › Article › peer-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 language	English
Journal	IEEE Transactions on Reliability
DOIs	https://doi.org/10.1109/TR.2020.3013158
Publication status	Accepted/In press - 2020

All Science Journal Classification (ASJC) codes

Safety, Risk, Reliability and Quality
Electrical and Electronic Engineering

Access to Document

10.1109/TR.2020.3013158

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

Cite this

@article{d8cccc23721b40b098c8634fb3f8ba30,

title = "Strong Reliability of Star Graphs Interconnection Networks",

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 $M$ of at most $3n-7$ processors is deleted from an $n$-star graph, the surviving graph has a large component of size greater or equal to $n!-|M|-3$. We then prove that when a set $M$ of at most $4n-9$ processors is deleted from an $n$-star graph, the surviving graph has a large component of size greater or equal to $n!-|M|-5$. Finally, we also calculate the $r$-component connectivity of the $n$-star graph for $2\leq r\leq 5$.",

author = "Limei Lin and Yanze Huang and Hsieh, {Sun Yuan} and Li Xu",

year = "2020",

doi = "10.1109/TR.2020.3013158",

language = "English",

journal = "IRE Transactions on Reliability and Quality Control",

issn = "0018-9529",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

TY - JOUR

T1 - Strong Reliability of Star Graphs Interconnection Networks

AU - Lin, Limei

AU - Huang, Yanze

AU - Hsieh, Sun Yuan

AU - Xu, Li

PY - 2020

Y1 - 2020

N2 - 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 $M$ of at most $3n-7$ processors is deleted from an $n$-star graph, the surviving graph has a large component of size greater or equal to $n!-|M|-3$. We then prove that when a set $M$ of at most $4n-9$ processors is deleted from an $n$-star graph, the surviving graph has a large component of size greater or equal to $n!-|M|-5$. Finally, we also calculate the $r$-component connectivity of the $n$-star graph for $2\leq r\leq 5$.

AB - 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 $M$ of at most $3n-7$ processors is deleted from an $n$-star graph, the surviving graph has a large component of size greater or equal to $n!-|M|-3$. We then prove that when a set $M$ of at most $4n-9$ processors is deleted from an $n$-star graph, the surviving graph has a large component of size greater or equal to $n!-|M|-5$. Finally, we also calculate the $r$-component connectivity of the $n$-star graph for $2\leq r\leq 5$.

UR - http://www.scopus.com/inward/record.url?scp=85091280871&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85091280871&partnerID=8YFLogxK

U2 - 10.1109/TR.2020.3013158

DO - 10.1109/TR.2020.3013158

M3 - Article

AN - SCOPUS:85091280871

JO - IRE Transactions on Reliability and Quality Control

JF - IRE Transactions on Reliability and Quality Control

SN - 0018-9529

ER -

Strong Reliability of Star Graphs Interconnection Networks

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Cite this