Search

Connectivity type measures form an important topic in graph theory. Such measures provide an important part of analyzing the vulnerability and resilience of interconnection networks. In this short commentary, we outline our perspective on the development of this topic with respect to interconnection networks. [ABSTRACT FROM AUTHOR]

We propose the complete cubic network structure to extend the existing class of hierarchical cubic networks, and establish a general connectivity result which states that the surviving graph of a complete cubic network, when a linear number of vertices are removed, consists of a large (connected) component and a number of smaller components which altogether contain a limited number of vertices. As applications, we characterize several fault-tolerance properties for the complete cubic network, including its restricted connectivity, i.e., the size of a minimum vertex cut such that the degree of every vertex in the surviving graph has a guaranteed lower bound; its cyclic vertex-connectivity, i.e., the size of a minimum vertex cut such that at least two components in the surviving graph contain a cycle; its component connectivity, i.e., the size of a minimum vertex cut whose removal leads to a certain number of components in its surviving graph; and its conditional diagnosability, i.e., the maximum number of faulty vertices that can be detected via a self-diagnostic process, in terms of the common Comparison Diagnosis model. [ABSTRACT FROM AUTHOR]

We suggest the notion ofH-centred surface area of a graph G, whereHis a subgraph ofG, i.e.the number of vertices in G at a certain distance from H, and focus on the special case whenHis a length two path to derive an explicit formula for the length two path-centred surface areas of the general and scalable arrangement graph. [ABSTRACT FROM AUTHOR]

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 FROM AUTHOR]

The conditional diagnosability of interconnection networks has been studied in a number of ad-hoc methods resulting in various conditional diagnosability results. In this paper, we utilize these existing results to give an unified approach in studying this problem. Following this approach, we derive the exact value of the conditional diagnosability for a number of interconnection networks including Cayley graphs generated by 2-trees (which generalize alternating group graphs), arrangement graphs (which generalize star graphs and alternating group graphs), hyper Petersen networks, and dual-cube like networks (which generalize dual-cubes.) [ABSTRACT FROM AUTHOR]

We derive an explicit formula for the surface area of the arrangement graph, i.e. the number of vertices at a certain distance from the identity vertex in such a graph. We also present such formulas for the star graph, the alternating group graph, and the split-star graph, via their respective structural relationship to the arrangement graph. [ABSTRACT FROM AUTHOR]

Abstract: We present an explicit formula for the surface area of the -star graph, i.e., the number of nodes at a certain distance from the identity node in the graph, by identifying the unique cycle structures associated with the nodes in the graph, deriving a distance expression in terms of such structures between the identity node of the graph and any other node, and enumerating those cycle structures satisfying the distance restriction. The above surface area derivation process can also be applied to some of the other node symmetric interconnection structures defined on the symmetric group, when the aforementioned distance expression is available. [Copyright &y& Elsevier]

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. In this paper, we give explicit formulas for the surface areas of the (n, k)-star graphs and the arrangement graphs via the generating function technique. As a direct consequence, these formulas will also provide such explicit formulas for the star graphs, the alternating group graphs and the split-stars since these graphs are related to the (n, k)-star graphs and the arrangement graphs. In addition, we derive the average distances for these graphs. [ABSTRACT FROM AUTHOR]

An introduction is presented in which the author discusses the topics include interconnection networks; class of hypergraphs; and diagnosability of networks.