Existence of optimally‐greatest digraphs for strongly connected node reliability

DOI10.1002/NET.22150MaRDI QIDQ6139368zbMATH OpenFDO

Authors Kyle MacKeigan, D. Cox

Publication date 18 December 2023

Published in Networks (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2206.12248

zbMATH Keywords

circulantsdigraphsnetwork reliabilityoptimalitypolynomialsstrongly connected

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Deterministic network models in operations research (90B10) Reliability, availability, maintenance, inspection in operations research (90B25)

Abstract: In this paper, we introduce a new model to study network reliability with node failures. This model, strongly connected node reliability, is the directed variant of node reliability and measures the probability that the operational vertices induce a subdigraph that is strongly connected. If we are restricted to directed graphs with $n$ vertices and $n+1leqmleq2n-3$ or $m=2n$ arcs, an optimally-greatest digraph does not exist. Furthermore, we study optimally-greatest directed circulant graphs when the vertices operate with probability $p$ near zero and near one. In particular, we show that the graph $Gammaleft(mathbb{Z}_n,1,-1ight)$ is optimally-greatest for values of $p$ near zero. Then, we determine that the graph $Gammaleft(mathbb{Z}_n,1,fracn+22ight)$ is optimally-greatest for values of $p$ near one when $n$ is even. Next, we show that the graph $Gammaleft(mathbb{Z}_n,1,2(3^{-1})ight)$ is optimally-greatest for values of $p$ near one when $n$ is odd and not divisible by three and that $Gammaleft(mathbb{Z}_n,1,3(2^{-1})ight)$ is optimally-greatest for values of $p$ near one when $n$ is odd and divisible by three. We conclude with a discussion of open problems.

Recommendations

• Uniformly optimal digraphs for strongly connected reliability
• The strongly connected reliability of complete digraphs
• On the existence of uniformly optimally reliable networks
• scientific article; zbMATH DE number 867686
• A proof of Boesch's conjecture

Cites work

• scientific article; zbMATH DE number 53165 (Why is no real title available?)
• Nonexistence of optimal graphs for all terminal reliability
• On the roots of strongly connected reliability polynomials
• On Ádám's conjecture for circulant graphs
• The closure of the set of roots of strongly connected reliability polynomials is the entire complex plane
• The Complexity of the Residual Node Connectedness Reliability Problem
• The strongly connected reliability of complete digraphs

This page was built for publication: Existence of optimally‐greatest digraphs for strongly connected node reliability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6139368)