Fault-tolerance and diagnosability of hierarchical star networks. Issue 2 (3rd April 2018) - Gu, Mei-Mei; Hao, Rong-Xia; Jiang, Lei
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.