UM
Residential Collegefalse
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 PublicationINTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS
ISSN0020-7160
Volume85Issue: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.

KeywordFault Tolerance Interconnection Network Largest Connected Component Star Graph
DOI10.1080/00207160701619200
URLView the original
Indexed BySCIE
Language英語English
WOS Research AreaMathematics
WOS SubjectMathematics, Applied
WOS IDWOS:000259928100003
Scopus ID2-s2.0-54049090846
Fulltext Access
Citation statistics
Document TypeJournal article
CollectionUniversity of Macau
Affiliation1.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.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Yang X.]'s Articles
[Megson G.M.]'s Articles
[Tang Y.Y.]'s Articles
Baidu academic
Similar articles in Baidu academic
[Yang X.]'s Articles
[Megson G.M.]'s Articles
[Tang Y.Y.]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Yang X.]'s Articles
[Megson G.M.]'s Articles
[Tang Y.Y.]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.