Residential College | false |
Status | 已發表Published |
Largest connected component of a star graph with faulty vertices | |
Yang X.3; Megson G.M.1; Tang Y.Y.3; Xing Y.3 | |
2008-12-01 | |
Source Publication | INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS
![]() |
ISSN | 0020-7160 |
Volume | 85Issue:12Pages:1771-1778 |
Abstract | In order to make a full evaluation of an interconnection network, it is essential to estimate the minimum size of a largest connected component of this network provided the faulty vertices in the network may break its connectedness. Star graphs are recognized as promising candidates for interconnection networks. This article addresses the size of a largest connected component of a faulty star graph. We prove that, in an n-star graph (n3) with up to 2n-4 faulty vertices, all fault-free vertices but at most two form a connected component. Moreover, all fault-free vertices but exactly two form a connected component if and only if the set of all faulty vertices is equal to the neighbourhood of a pair of fault-free adjacent vertices. These results show that star graphs exhibit excellent fault-tolerant abilities in the sense that there exists a large functional network in a faulty star graph. |
Keyword | Fault Tolerance Interconnection Network Largest Connected Component Star Graph |
DOI | 10.1080/00207160701619200 |
URL | View the original |
Indexed By | SCIE |
Language | 英語English |
WOS Research Area | Mathematics |
WOS Subject | Mathematics, Applied |
WOS ID | WOS:000259928100003 |
Scopus ID | 2-s2.0-54049090846 |
Fulltext Access | |
Citation statistics | |
Document Type | Journal article |
Collection | University of Macau |
Affiliation | 1.University of Reading 2.Hong Kong Baptist University 3.Chongqing University |
Recommended Citation GB/T 7714 | Yang X.,Megson G.M.,Tang Y.Y.,et al. Largest connected component of a star graph with faulty vertices[J]. INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2008, 85(12), 1771-1778. |
APA | Yang X.., Megson G.M.., Tang Y.Y.., & Xing Y. (2008). Largest connected component of a star graph with faulty vertices. INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 85(12), 1771-1778. |
MLA | Yang X.,et al."Largest connected component of a star graph with faulty vertices".INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 85.12(2008):1771-1778. |
Files in This Item: | There are no files associated with this item. |
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment