Fault-tolerance and diagnosability of hierarchical star networks
Mei-Mei Gu, Rong‐Xia Hao, Lei Jiang · International Journal of Computer Mathematics Computer Systems Theory · 2018
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 4n−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.