Abstract With the growing scale and complexity of high-performance computing systems, ensuring reliability through robust fault diagnosis becomes increasingly critical. System-level diagnosis plays a key role in identifying faulty processors and maintaining system stability of multiprocessor systems. However, traditional diagnosability, as a global reliability metric for multiprocessor systems, overlooks local diagnostic capability, topological criticality, and fault distribution. In order to better capture the local characteristics of a system around a given node, this work proposes a novel fault diagnosis strategy, called cyclic local diagnosability, where the cyclic fault pattern requires that at least two components contain cycles. We propose some characterizations of cyclic local diagnosability of interconnection networks under PMC and MM* models. As applications, we determine the cyclic local diagnosabilities of data center network DCell ($D_{k,n}$), $(n,k)$-star graph ($S_{n,k}$) and $(n,k)$-bubble-sort graph ($B_{n,k}$) under PMC and MM* models. Finally, we show the superiority of the cyclic local diagnosability through comparison with other conditional diagnosabilities.

With the proliferation of interconnection networks in mission-critical systems ranging from cloud computing infrastructures to large-scale data centers, the escalating structural complexity has intensified network vulnerability to malicious attacks and cyber warfare incidents. This article establishes a theoretical framework for evaluating network self-diagnostic capability through a novelh-extrar-component diagnosability metric, denoted as$\widehat{ec}_{r}^{h}(G)$, which quantifies a network’s resilience under compound fault patterns. The proposed metric requires that after removing specific nodes, the remaining subgraph is required to preserve at leastrconnected components where every component maintains a node count exceedingh. Through rigorous combinatorial analysis, we derive closed-form expressions for star networks$S_{n}$,$\widehat{ec}_{2}^{1}(S_{n}) = 4n - 9$and$\widehat{ec}_{3}^{1}(S_{n}) = 6n - 15$when$n \ge 6$, establishing the tight diagnosability bounds for this fundamental network topology. To enable practical implementation, we design a Trial System-based Fault Diagnosis Algorithm (TSFD) that features adaptive syndrome verification and parallel fault localization mechanisms. Extensive simulations demonstrate the accuracy of 98.99% fault detection with linear-time complexity$O(Nd)$inn-dimensional star networks. This work advances network reliability theory by introducing a multi-feature diagnosability measure for system-level diagnosis and developing an efficient diagnosis algorithm validated through large-scale network emulation.

Let $G$ be a graph and $S\subseteq V(G)$ with $|S|\geq 2$. Then the trees $T_1, T_2, \cdots, T_\ell$ in $G$ are \emph{internally disjoint Steiner trees} connecting $S$ (or $S$-Steiner trees) if $E(T_i) \cap E(T_j )=\emptyset$ and $V(T_i)\cap V(T_j)=S$ for every pair of distinct integers $i,j$, $1 \leq i, j \leq \ell$. Similarly, if we only have the condition $E(T_i) \cap E(T_j )=\emptyset$ but without the condition $V(T_i)\cap V(T_j)=S$, then they are \emph{edge-disjoint Steiner trees}. The \emph{generalized $k$-connectivity}, denoted by $κ_k(G)$, of a graph $G$, is defined as $κ_k(G)=\min\{κ_G(S)|S \subseteq V(G) \ \textrm{and} \ |S|=k \}$, where $κ_G(S)$ is the maximum number of internally disjoint $S$-Steiner trees. The \emph{generalized local edge-connectivity} $λ_{G}(S)$ is the maximum number of edge-disjoint Steiner trees connecting $S$ in $G$. The {\it generalized $k$-edge-connectivity} $λ_k(G)$ of $G$ is defined as $λ_k(G)=\min\{λ_{G}(S)\,|\,S\subseteq V(G) \ and \ |S|=k\}$. These measures are generalizations of the concepts of connectivity and edge-connectivity, and they and can be used as measures of vulnerability of networks. It is, in general, difficult to compute these generalized connectivities. However, there are precise results for some special classes of graphs. In this paper, we obtain the exact value of $λ_{k}(S(n,\ell))$ for $3\leq k\leq \ell^n$, and the exact value of $κ_{k}(S(n,\ell))$ for $3\leq k\leq \ell$, where $S(n, \ell)$ is the Sierpiński graphs with order $\ell^n$. As a direct consequence, these graphs provide additional interesting examples when $λ_{k}(S(n,\ell))=κ_{k}(S(n,\ell))$. We also study the some network properties of Sierpiński graphs. Steiner Tree; Generalized Connectivity; Sierpiński Graph

Abstract Motivated by a multitude of practical applications, many distinct vulnerability parameters of multiprocessor systems have been explored. Traditional connectivity and diagnosability are undoubtedly the most well investigated of these metrics, but often fail to capture the most subtle differences of a multiprocessor system. Subsequently, it is necessary to take into account the minimum degree of components, the size of components or the number of components. However, the structure of the components is ignored in these circumstances. In this work, we propose a novel diagnostic strategy based on cyclic connectivity, namely the cyclic diagnosability. The cyclic diagnosability, denoted by $ct(G)$, is the maximum size of the faulty vertex set $F$ of $G$ such that the self-diagnosable system $G$ can identify all the vertices in $F$ under the condition that at least two connected components of $G-F$ contain a cycle. Furthermore, we investigate the cyclic diagnosability of hypercube $Q_{n}$ under the PMC model and the MM* model, and show that $ct(Q_{n})=5n-10$ for $n\geq 7$.

The reliability of interconnection network ordinarily is measured by two significant indexes, namely, connectivity and diagnosability. The qualitative and quantitative reliability analysis relies on the choice of an appropriate mathematical modeling and assumptions consistent with the actual situation. The cyclic connectivity is a well-established index to evaluate the reliability of interconnection network. For a network$\mathbb{G}$, we use$\kappa _{c}(\mathbb{G})$to denote cyclic connectivity of$\mathbb{G}$, which is the minimum size of the node cut set$D$such that$\mathbb{G}-D$is disconnected and at least two of its components have cycles. Based on the cyclic connectivity, cyclic diagnosability ($ct(\mathbb{G})$) is proposed to measure the self-diagnostic capability of the networks. Up to this day, the cyclic connectivity of some special networks has been determined successfully, but the cyclic diagnosability of a great deal of networks is still up in the air. In this work, we investigate the measurable relationship between cyclic connectivity and 2-good connectivity under certain restrictions. Furthermore, we characterize the cyclic diagnosability of a class of networks in terms of character commonality of the networks. To be more specific, we show that$ct(\mathbb{G})=\kappa _{c}(\mathbb{G})+(l-k)$under the PMC model (PMC-M) and the MM$^\ast$model (MM$^\ast$-M), where$l$is the regular degree of network and$l\geq 3, 1\leq k< l$are constant. Then, we directly determine the cyclic diagnosability of hypercubes, locally twisted cubes, and alternating group networks. Finally, we compare the cyclic diagnosability of the network with other kinds of restricted diagnosabilities. The results show that cyclic diagnosability has excellent self-diagnostic capability.

An important invariant of an interconnection network is its surface area, the number of vertices at distance i from a node. Although much work has been done to obtain formulas for the surface areas for many interconnection networks, most of the formulas are not in the so-called closed form except for a very few trivial graphs. It is known that for an interconnection network, if its surface area satisfies the so-called forward difference property, then for any specific distance i, its surface area of radius i in closed form (a polynomial of degree i) can be obtained, provided that we have i + 1 initial values of the surface area of radius i. This property is known to hold for the hypercube and the star graph. We show in this paper that the property also holds for the (n, k)-star graph, 1 ≤ k ≤ n − 1, a family of interconnection networks that also include the star graph when k = n − 1. We then show that the technique we use for the result is general that can also be used to prove the property for some other networks.

Abstract Reliability of a multiprocessor system becomes an important issue for parallel computing. Component diagnosability and component connectivity of a graph play crucial roles in assessing the vulnerability of an interconnection network, which are two significant indicators for the reliability and fault tolerance of a multiprocessor system. Until now, only a little knowledge of results have been known on $r$-component diagnosability and $r$-component connectivity. In this paper, we first propose the $r$-component diagnosability of $n$-dimensional alternating group graph $AG_{n}$ under PMC model. And then we promote our research on $AG_{n}$ by a fairly good construction for general $r$-component connectivity of $AG_{n}$, where $6\leq r\leq n-1$. The theoretical analysis and simulation show that the general $r$-component connectivity of $AG_{n}$ is larger than those of $Q_{n}$, $D_n$ and $FQ_{n}$.

Abstract Diagnosability is an important metric to fault tolerance and reliability for multiprocessor systems. However, plenty of research on fault diagnosability focuses on node failure. In practical scenario, not only node failures take place but also link malfunctions may arise. In this work, we investigate the diagnosability of general regular networks with failing nodes as well as missing malfunctional links. Let $S$ be a set of the missing links and broken-down nodes. We first prove that the diagnosability of the survival graph $G\setminus S$ persists $\delta (G\setminus S)$ under the PMC model (Preparata, F.P., Metze, G. and Chien, R.T. (1967) On the connection assignment problem of diagnosable systems. IEEE Trans. Electron. Comput., EC-16, 848–854) for a $t$-regular and $t$-connected triangle-free network $G$ subject to $|S|\leq t-1$ and $|V(G)|\geq 3t-2$ ($t\geq 3$). Furthermore, we determine the diagnosability of $G\setminus S$ for some kinds of extensively explored $t$-regular networks with triangles subject to $|S|\leq t-1$ ($t\geq 3$).

Abstract Most graphs have this property: after removing a linear number of vertices from a graph, the surviving graph is either connected or consists of a large connected component and small components containing a small number of vertices. This property can be applied to derive fault-tolerance related network parameters: extra edge connectivity and component edge connectivity. Using this general property, we obtained the $h$-extra edge connectivity and $(h+2)$-component edge connectivity of augmented cubes, Cayley graphs generated by transposition trees, complete cubic networks (including hierarchical cubic networks), generalized exchanged hypercubes (including exchanged hypercubes) and dual-cube-like graphs (including dual cubes).

Processor fault diagnosis has played an essential role in measuring the reliability of a multiprocessor system. The diagnosability of many well-known multiprocessor systems has been widely investigated. Conditional diagnosability is a novel measure of diagnosability by adding a further condition that any fault set cannot contain all the neighbors of every node in the system. Several known structural properties of Cayley graphs are exhibited. Based on these properties, we investigate the conditional diagnosability of Cayley graphs generated by transposition trees under the PMC model and show that it is 4n-11 for n ≥ 4 except for the n -dimensional star graph for which it has been shown to be 8 n -21 for n ≥ 5 (refer to Chang and Hsieh [2014]).

An important and interesting parameter of an interconnection network is the number of vertices of a specific distance from a specific vertex. This is known as the surface area or the Whitney number of the second kind. It turns out that, in some applications, the number of vertices of a specific distance from a subgraph H is also important. A fundamental starting point is to consider the number of vertices of a specific distance from an edge, which is called the edge surface area. In this paper, we give an explicit formula for the edge surface area of arrangement graphs via the generating function technique. As a direct consequence, it will also provide such explicit formulas for star graphs, alternating group graphs and split stars.

Abstract The star graph proposed by Akers et al. (Proc Int Conf Parallel Process, University Park, PA, 1987, pp. 393–400) has many advantages over the n‐cube. However, it suffers from having large gaps in the possible number of vertices. The arrangement graph was proposed by Day and Tripathi (Inf Process Lett 42 (1992), 235–241) to address this issue. Since it is a generalization of the star graph, it retains many of the nice properties of the star graph. In fact, it also generalizes the alternating group graph (Jwo et al., Networks 23 (1993), 315–326). There are many different measures of structural integrity of interconnection networks. In this article, we prove results of the following type for the arrangement graph: If h(r,n,k) vertices are deleted from the arrangement graph An,k, the resulting graph will either be connected or have a large component and small components having at most r − 1 vertices in total. Our result is tight for r ≤ 3, and it is asymptotically tight for r ≥ 4. Moreover, we also determine the cyclic vertex‐connectivity of the arrangement graph. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013

Abstract The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost‐perfect matchings. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. Recently, the conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond those induced by a single vertex. This number is defined to be the minimum number of edges whose deletion results in a graph with no isolated vertices that has neither perfect matchings nor almost‐perfect matchings. In this article, we prove general results regarding the matching preclusion number and the conditional matching preclusion number as well as the classification of their respective optimal sets for bipartite graphs. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011

Abstract The matching preclusion number of a graph with an even number of vertices is the minimum number of edges whose deletion results in a graph that has no perfect matchings. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. It is natural to look for obstruction sets beyond those induced by a single vertex. The conditional matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph with no isolated vertices that has no perfect matchings. In this companion paper of Cheng et al. (Networks (NET 1554)), we find these numbers for a number of popular interconnection networks including hypercubes, star graphs, Cayley graphs generated by transposition trees and hyper‐stars. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011

The size and complexity of medical record databases makes extracting information challenging. With the tables numbering in thousands, even database analysts have trouble finding important fields and discovering various associations between tables. This paper presents a case study of our initial method of finding minimum Steiner trees in the Epic Clarity Reporting database to solve this problem. In addition, we present a web service architecture that can be used to extend our approach to multiple databases.

Abstract In this article we consider a class of Cayley graphs that are generated by certain 3‐cycles on the alternating group An. These graphs are generalizations of the alternating group graph AGn. We look at the case when the 3‐cycles form a “tree‐like structure,” and analyze its fault resiliency. We present a number of structural theorems and prove that even with linearly many vertices deleted, the remaining graph has a large connected component containing almost all vertices. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

Abstract The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost‐perfect matchings. In this paper, we find this number for various classes of interconnection networks and classify all the optimal solutions. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(2), 173–180 2007

Abstract The class of star graphs is a popular topology for interconnection networks. However, it has certain deficiencies. A class of generalization of star graphs called (n,k)‐star graphs was introduced by Chiang and Chen to address these issues. In this article we will consider the vertex‐connectivity of the directed (n,k)‐star graph,$\overrightarrow{S_{n,k}}$ , given by Cheng and Lipman, 8 , and show that it is maximally connected. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 46(3), 154–162 2005

Abstract The star graph Sn proposed by Akers et al. has many advantages over the n‐cube. We show that when a large number of vertices are deleted from Sn the resulting graph can have at most two components, one of which is small. We use this result to solve a successive augmentation problem for Sn. This, in turn, provides extra choices for the topology of large interconnection networks. © 2002 Wiley Periodicals, Inc.

A large class of facets is constructed for the stable set polytope. This class is a common generalization of wheel facets and of antiweb facets. The proof of their validity and facetness exploits graph operations which transform inequalities into more complicated ones. In an accompanying paper polynomial time separation-algorithms are presented for generalizations of these inequalities.

Akers et al. proposed an interconnection topology, the star graph, as an alternative to the popular n-cube. Cheng et al. proposed the split-star as an alternative to the star graph and a companion graph to the alternating group graph proposed by Jwo et al. Star graphs, alternating group graphs, and split-stars are advantageous over n-cubes in many aspects. Day and Tripathi proposed an assignment of directions to the edges of the star graph and showed that the resulting directed graph is strongly connected and has a simple routing algorithm. In this paper, we give simple routing algorithms for a proposed orientation of alternating group graphs and split-stars. The resulting directed graphs are not only strongly connected but they have maximal arc-fault tolerance and a small diameter. © 2000 John Wiley & Sons, Inc.