Fault diagnosability of data center networks

A kind of generalization of diagnosability for a network G is g-good-neighbor diagnosability which is denoted by t(g)(G). Let K-g(G) be the R-g-connectivity. Lin et al. (2016) [17] and Xu et al. (2017) [29] gave the same problem independently that: the relationship between the R-g-connectivity K-g(G) and t(g)(G) of a general graph G needs to be studied in the future. In this paper, this open problem is solved for general regular graphs. We firstly establish the relationship of K-g(G) and t(g)(G), and obtain that t(g)(G) = K-g(G) + g under some conditions. Secondly, we obtain the g-good-neighbor diagnosability of data center network D-k,D-n which are t(g)(D-k,D-n) = (g +1)(k - 1) + n + g for 1 <= g <= n - 1 under the PMC model and the MM* model, respectively. Furthermore, we show that D-k,D-n is tightly super (n + k - 1)-connected for n >= 2 and k >= 2 and we also prove that the largest connected component of the survival graph contains almost all of the remaining vertices in D-k,D-n when n + 2k - 2 vertices removed. (C) 2019 Elsevier B.V. All rights reserved.