Abstract In 1966, Chartrand proved that if the minimum degree of a graph is at least the floor of half the number of nodes, then its edge‐connectivity equals its minimum degree. A more discriminating notion of edge‐connectivity is introduced, called the k‐component order edge‐connectivity, which is the minimum number of edges required to be removed so that the order of each component of the resulting subgraph is less than k. Results are established that guarantee that this parameter is at least as large as the minimum degree, provided the minimum degree is sufficiently large. This generalizes Chartrand's result. It is also determined when these results are best possible. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

Abstract The purpose of this article is to introduce several results concerning the analysis and synthesis of reliable or invulnerable networks. First, the notion of signed reliability domination of systems is described and some applications to reliability analysis are reviewed. Then the analysis problem is considered and a brief summary of the difficulty of calculating various reliability measures is presented. Some relevant concepts in the synthesis of a most reliable network are studied. The article concludes with an introduction to a non‐probabilistic approach to evaluate the vulnerability of a network. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

We give an algebraic characterization of the generating sets of Cayley graphs with neighbor connectivity equal to one for a class of Cayley graphs that includes the Cayley graphs of all abelian groups. We also show that the determination of the neighbor connectivity of a graph is NP-hard.

Graph G has perfectly reliable nodes and edges that are subject to stochastic failure. The network reliability R is the probability that the surviving edges induce a spanning connected subgraph of G. Analysis problems concern determining efficient algorithms to calculate R, which is known to be NP-hard for general graphs. Synthesis problems concern determining graphs that are, according to some definition, the most reliable in the class of all graphs having a given number of edges and nodes. In applications where the edges are perfectly reliable and the nodes are subject to failure, another measure (residual node connectedness reliability) is defined as the probability that the surviving nodes induce a connected subgraph of G. Referring to such a subset as an operating state, the measure is not coherent because a superset of an operating state need not be an operating state. This paper proposes a new definition of network reliability that handles the case of node failures; it is coherent. We determine many of its properties, and present several analysis and synthesis results.

Abstract This paper considers a probabilistic graph in which the points are perfectly reliable but the edges operate independently of one another, all with some known probability p. The graph G is in an operating state if the surviving edges induce a spanning connected subgraph of G. The all‐terminal reliability R(G,p) of G is the probability that G is in an operating state. A graph transformation, called “the swing surgery,” is introduced, and it is shown that this surgery has important properties. First, if H is the graph obtained by deleting m independent edges from the complete graph, then for any other graph G with the same number of points and edges as H, R(H,p) > R(G,p) for all 0 < p < 1. Moreover, the swing surgery yields a simple topological proof of the well‐known result that H has more spanning trees than does G. Another important consequence is that given any graph G there exists a threshold graph T with the same number of points and edges as G such that R(T,p) ≤ R(G,p) for all 0 < p < 1.

Abstract A well‐known model for network reliability studies consists of an undirected graph with perfectly reliable nodes and equal and independent edge failure probabilities. The measure of reliability is then defined to be the probability that the graph is connected. A well‐defined synthesis problem is to find the graph that minimizes the failure probability given the number of nodes n, the number of edges e, and the edge failure rate ρ. In this work, we consider the possibility of the existence of a fixed graph that is optimal for all possible ρ. It is simple to verify that such graphs exist when e = n − 1, or n. Herein, we show that they also exist when e = n + 1 and n + 2.

This paper considers a probabilistic network in which the edges are perfectly reliable but the nodes fail with some known probabilities. The network is in an operational state if the surviving nodes induce a connected graph. The residual node connectedness reliability $R(G)$ of a network G is the probability that the graph induced by the surviving nodes is connected. This reliability measure is very different from the widely studied K-terminal network reliability measure. It is proven that the problem of computing the residual connectedness reliability is NP-hard by showing that the problem of counting the number of node induced connected subgraphs of a given graph is $# {\bf P}$-complete. The problem remains $# {\bf P}$-complete for split graphs as well as planar and bipartite graphs.

A well-known model in communication network reliability consists of an undirected graph G whose edges operate independently with the same probability p. Then the reliability, R(G,p) of G, is the probability that G is connected. It is known that R(G,p) is a polynomial in p and its coefficient of the least-order term is the number of spanning trees t(G), while the coefficient of the highest-order term is the reliability domination d(G) of G. Presented is a complete characterization of graphs that achieve the minimum absolute value mod d(G) mod over the class of n-node, e-edge connected graphs. Furthermore, the class of graphs that yield minimum t(G) is shown to minimize mod d(G) mod . The results have applications in the synthesis of least-reliable networks.>

Abstract This paper presents some results regarding the design of reliable networks. The problem under consideration involves networks which are undirected graphs having equal and independent edge failure probabilities. The index of reliability is the probability that the network fails (becomes disconnected). For “small” edge failure probabilities and given p and q there exists a class of p vertex, q edge graphs with the property that any graph in the class has a smaller probability of disconnection than any graph outside of the class. We solve the problem of synthesizing graphs in this class.

Abstract It is well known that certain graph‐theoretic extremal questions play a central role in the study of information network vulnerability. These extremal problems are special cases of the general question of realizability of graph invariants. For example a (p, Δ, δ, λ) graph is a graph having p‐points, maximum degree Δ, minimum degree δ, and line‐connectivity λ. An arbitrary quadruple of integers (a, b, c, d) is called (p, Δ, δ, γ) realizable if there is a (p, Δ, δ, γ) graph with p = a, Δ = b, δ = c, and γ = d. Necessary and sufficient conditions for a quadruple to be (p, Δ, δ, γ) realizable were recently given by the authors. In another manuscript they gave the solution to (p, Δ, δ, k) realizability, where k denotes the point connectivity. In this work we give necessary and sufficient conditions for (p, q, k), (p, q, γ), and (p, q, δ) realizability, where q denotes the number of lines of a graph.