If G is a simple graph and ρ ∈ [ 0 , 1 ] , the reliability R G ( ρ ) is the probability of G being connected after each of its edges is removed independently with probability ρ . A simple graph G is a uniformly most reliable graph (UMRG) if R G ( ρ ) ≥ R H ( ρ ) for every ρ ∈ [ 0 , 1 ] and every simple graph H on the same number of vertices and edges as G . Boesch (1986) conjectured that, if n and m are such that there exists a connected simple graph on n vertices and m edges, then there also exists a UMRG on the same number of vertices and edges. Some counterexamples to Boesch’s conjecture were given by Kelmans, Myrvold et al., and Brown and Cox. It is known that Boesch’s conjecture holds whenever the corank, defined as c = m − n + 1 , is at most 4 (and the corresponding UMRGs are fully characterized). Ath and Sobel conjectured that Boesch’s conjecture holds whenever the corank c is between 5 and 8, provided the number of vertices is at least 2 c − 2 . In this work, we give an infinite family of counterexamples to Boesch’s conjecture of corank 5. These are the first reported counterexamples that attain the minimum possible corank. As a byproduct, the conjecture by Ath and Sobel is disproved.

ABSTRACT Let be the set of connected simple graphs on vertices and edges. Define the corank of as . Let be in and . The reliability is the probability of being connected after each of its edges is removed independently with probability . The graph is a uniformly most reliable graph (UMRG) if for every in and for all . In 1986, Boesch conjectured that each nonempty class contains at least one UMRG. A few years later, Boesch et al. and Wang proved that each class having corank up to 4 includes one UMRG. However, infinitely many counterexamples to the Boesch conjecture appeared. Ath and Sobel conjectured that the Boesch conjecture holds when the corank is between 5 and 8, provided the number of vertices is at least . Recently, it was proved that there are only finitely many UMRGs having corank 5, in strong contrast with graph classes having corank up to 4. A natural question is the existence of UMRGs having corank 6. Here, it is proved that for each positive integer there is no UMRG on vertices having corank 6. This result provides new families of counterexamples to the Boesch and Ath‐Sobel conjectures proposed respectively in 1986 and 2000.

A two-terminal graph is a simple graph equipped with two distinguished vertices, called terminals. Let T n , m be the class consisting of all nonisomorphic two-terminal graphs on n vertices and m edges. Let G be any two-terminal graph in T n , m , and let d be any positive integer. For each ρ ε [0,1], the d-constrained two-terminal reliability of G at ρ , denoted R G d (ρ), is the probability that G has some path of length at most d joining its terminals after each of its edges is independently deleted with probability ρ . We say G is a d-uniformly most reliable two-terminal graph ( d -UMRTTG) if for each H in T n , m and every ρ ε [0,1] it holds that R G d (ρ) ≥ R H d (ρ). Previous works studied the existence of d -UMRTTG in T n , m when d is greater than or equal to n - 1, or equivalently, when the distance constraint is dropped. In this work, a characterization of all 1-UMRTTGs and 2-UMRTTGs is given. Then, it is proved that there exists a unique 3-UMRTTG in T n , m when n ≥ 6 and 5 ≤ m ≤ 2n - 3. Finally, for each d ≥ 4 and each n ≥ 11 it is proved that there is no d -UMRTTG in T n , m when 20 ≤ m ≤ 3n - 9 or when 3n − 5 ≤ m≤ (n 2) − 2.

A longstanding problem in spectral graph theory asks for graphs with maximum number of spanning trees among all connected simple graphs with a prescribed number of vertices and edges. Such graphs are called t -optimal graphs. Petingi and Rodríguez [Discrete Math. 244 (2002), 351–373] achieved in finding infinitely many t -optimal graphs. Basically, they reduced the problem of finding t -optimal graphs to the determination of almost-regular graphs with minimum number of induced 3-paths. In this work we revisit the construction of t -optimal graphs given by Petingi and Rodríguez. Then, we generalize the previous construction using the key concept of trace-minimal graph introduced by Ábrego et al. [Linear Algebra Appl. 412 (2006) 161–221]. Finally, as a consequence, we construct infinitely many new t -optimal regular graphs.

If G is a simple graph and ρ ϵ [0, 1], the reliability Rg(ρ) is the probability of G being connected after each of its edges is removed independently with probability ρ. A simple graph G is a uniformly most reliable graph (UMRG) if Rg(ρ) ≥ Rh(ρ) for every ρ ϵ [0, 1] and every simple graph H on the same number of vertices and edges as G. Boesch [J. Graph Theory 10 (1986), 339-352] conjectured that, if n and m are such that there exists a connected simple graph on n vertices and m edges, then there also exists a UMRG on the same number of vertices and edges. Some counterexamples to Boesch's conjecture were given by Kelmans, Myrvold et al., and Brown and Cox. It is known that Boesch's conjecture holds whenever the corank, defined as c = m - n + 1, is at most 4 (and the corresponding UMRGs are fully characterized). Ath and Sobel conjectured that Boesch's conjecture holds whenever the corank c is between 5 and 8, provided the number of vertices is at least 2c - 2. In this work, we give an infinite family of counterexamples to Boesch's conjecture of corank 5. These are the first reported counterexamples that attain the minimum possible corank. As a byproduct, the conjecture by Ath and Sobel is disproved.

Abstract Given its wide spectrum of applications, the classical problem of all‐terminal network reliability evaluation remains a highly relevant problem in network design. The associated optimization problem—to find a network with the best possible reliability under multiple constraints—presents an even more complex challenge, which has been addressed in the scientific literature but usually under strong assumptions over failures probabilities and/or the network topology. In this work, we propose a novel reliability optimization framework for network design with failures probabilities that are independent but not necessarily identical. We leverage the linear‐time evaluation procedure for network reliability in the series‐parallel graphs of Satyanarayana and Wood (1985) to formulate the reliability optimization problem as a mixed‐integer nonlinear optimization problem. To solve this nonconvex problem, we use classical convex envelopes of bilinear functions, introduce custom cutting planes, and propose a new family of convex envelopes for expressions that appear in the evaluation of network reliability. Furthermore, we exploit the refinements produced by spatial branch‐and‐bound to locally strengthen our convex relaxations. Our experiments show that, using our framework, one can efficiently obtain optimal solutions in challenging instances of this problem.

Abstract An enigmatic conjecture in network synthesis asserts that uniformly most reliable multigraphs are simple. Daniel Gross and John Saccoman proved in 1998 that the answer is affirmative whenever , where and are the number of nodes and edges of the multigraphs, respectively. They conjectured that the optimality is also achieved by simple graphs when . A proof for this conjecture recently appeared. In this article we provide a unified short proof for the previous cases where . Our proof strategy holds whenever the most reliable simple graphs satisfy the self‐similarity property. As a consequence, it could be used to study the multigraph conjecture for larger graph classes.

Abstract Which is the most reliable graph withnnodes andmedges? This celebrated problem has several aspects, according to the notion of optimality (in a local or uniform sense), failure type (either nodes or edges), or reliability model (all‐terminal connectedness, two‐terminal or multiterminal setting). This article presents a chronological survey of the multiple proposals to address the problem, together with recent trends and enigmatic conjectures posed decades ago that promote further research.

Consider a graph with perfect nodes and edges subject to independent random failures with identical probability. Theall-terminal reliabilityis the probability that the resulting subgraph is connected. First, we fully characterize uniformly least reliable graphs (ULRG) whose co-rank is not greater than four. Universal reliability bounds are here introduced for those graphs. It is formally proved that ULRG is invariant under bridge-contractions, and maximize the number of bridges among all connected simple graphs with a prescribed number of nodes and edges. A closed-form for the maximum number of bridges is also given, which has an intrinsic interest from a graph-theoretic point of view. Finally, the cost-reliability tradeoff is discussed, comparing the number of edges required to reduce the reliability gaps between the least and most reliable graphs. A remarkable conclusion is that the network design is critical under rare event failures, where the reliability-gap between least and most-reliable networks is monotonically increasing with the number of terminals.

Abstract Consider a graph with perfect nodes but independent edge failures with identical probability ρ. The reliability is the connectedness probability of the random graph. A graph with n nodes and e edges is uniformly optimally reliable (UOR) if it has the greatest reliability among all graphs with the same number of nodes and edges, for all values of ρ. In 1997, Gross and Saccoman proved that the simple UOR graphs for e = n, e = n + 1 and e = n + 2 are also optimal when the classes are extended to include multigraphs. The authors conjectured that the UOR simple graphs for e = n + 3 are optimal in multigraphs as well. A proof of the Gross–Saccoman conjecture is introduced.

In classical network reliability, the system under study is a network with perfect nodes and imperfect links that fail randomly and independently. The probability that a given subset of terminal nodes belongs to the same connected component is called classical or ‐Terminal reliability. Although (and because) the classical reliability computation belongs to the class of ‐Hard problems, the literature offers many methods for this purpose, given the importance of the models. This article deals with diameter‐constrained reliability, where terminal nodes are further required to be connected by hops or fewer ( is a given strictly positive parameter of the metric called its diameter). This metric was defined in 2001, inspired by delay‐sensitive applications in telecommunications. Factorization theory is fundamental for the classical network reliability evaluation, and today it is a mature area. However, its extension to the diameter‐constrained context requires at least the recognition of irrelevant links, which is an open problem. In this article, irrelevant links are efficiently determined in the most used case, where , thus providing a first step toward a Factorization theory in diameter‐constrained reliability. We also analyze the metric in series‐parallel and composition graphs. The article closes with a Factoring algorithm and a discussion of trends for future work. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(4), 283–291 2017

Let be a simple graph with vertices and edges, a subset of terminals, a vector and a positive integer , called the diameter. We assume vertices are perfect but edges fail stochastically and independently, with probabilities . The diameter constrained reliability (DCR) is the probability that the terminals of the resulting subgraph remain connected by paths composed of or fewer edges. This number is denoted by . The general DCR computation problem belongs to the class of ‐hard problems. The contributions of this article are threefold. First, the computational complexity of DCR‐subproblems is discussed in terms of the number of terminal vertices and the diameter . Either when or when and is fixed, the DCR problem belongs to the class of polynomial‐time solvable problems. The DCR problem becomes ‐hard when is a fixed input parameter and . The cases where or is a free input parameter and is fixed have not been studied in the prior literature. Here, the ‐hardness of both cases is established. Second, we categorize certain classes of graphs that allow the DCR computation to be performed in polynomial time. We include graphs with bounded corank, graphs with bounded genus, planar graphs, and in particular, Monma graphs, which are relevant in robust network design. Third, we introduce the problem of analyzing the asymptotic properties of the DCR measure in networks that grow infinitely following given probabilistic rules. We introduce basic results for Gilbert's random graph model. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(4), 296–305 2015

We propose a mathematical model to minimize the expected download time of cloud assisted Peer-to-Peer video on demand services. First, we define a simple fluid model that quantifies the evolution of peers, which are grouped into different classes regarding the number of concurrent video downloads. Then, analytical expressions for the expected download time are obtained under steady state, via Little's law. The goal is to minimize the expected download time with limited storage capacity in cache nodes of the network, called super-peers. The nature of this combinatorial problem is similar to the Multi-Knapsack Problem (MKP): the number of copies must be chosen for each video stream, with storage capacity constraints. We resolve the problem with a greedy randomized technique. The performance of this co-operative system is compared with a traditional content delivery network. Finally, the new caching policy is tested in a real scenario. The results confirm that the swarm assisted peer-to-peer service is both more economical and suitable to address massive scenarios, whereas the performance of both systems is similar in small scale instances.