Fault-tolerance and diagnosability of hierarchical star networks. Issue 2 (3rd April 2018)

• Record Type: Journal Article
• Authors: Gu, Mei-Mei; Hao, Rong-Xia; Jiang, Lei
• Is Part Of: International journal of computer mathematics. Volume 3:Issue 2(2018)
• Page Start: 106
• Page End: 121
• Publication Date: 2018-04-03
• Subjects: Hierarchical star networks -- extra connectivity -- fault-tolerance -- conditional diagnosability -- extra conditional diagnosability; Computer systems -- Periodicals; Computer systems; Periodicals; 004
• DOI: 10.1080/23799927.2018.1467488
• Languages: English
• ISSNs: 2379-9927

Abstract

ABSTRACT: The hierarchical star networks, proposed by Shi and Srimani, is a new level network topology and uses the star graphs as building blocks. Given a graph G, the h -extra connectivity of G is the minimum cardinality of a set of vertices in G, if exists, whose deletion disconnects G and leaves every remaining component with more than h vertices. There is no known polynomial-time algorithm for finding for a given graph G . In this paper, by exploring the combinatorial properties and fault-tolerance of, we show that the largest component of a survival graph contains almost all of the remaining vertices after removing at most 4 n −8 vertices and obtain the h -extra connectivity for of, where . As applications, the conditional diagnosability and the h -extra conditional diagnosability for of under the PMC model and the MM* model, respectively, are obtained.