On the split reliability of graphs

DOI10.1002/NET.22166MaRDI QIDQ6139376zbMATH OpenOpenAlexFDO

Authors Jason I. Brown

Publication date 18 December 2023

Published in Networks (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

graphoptimalall-terminal reliabilitytwo-terminal reliabilitysplit reliability

Mathematics Subject Classification ID

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

Abstract: A common model of robustness of a graph against random failures has all vertices operational, but the edges independently operational with probability $p$. One can ask for the probability that all vertices can communicate ({em all-terminal reliability}) or that two specific vertices (or {em terminals}) can communicate with each other ({em two-terminal reliability}). A relatively new measure is {em split reliability}, where for two fixed vertices $s$ and $t$, we consider the probability that every vertex communicates with one of $s$ or $t$, but not both. In this paper, we explore the existence for fixed numbers $ngeq2$ and $mgeqn-1$ of an {em optimal} connected $(n,m)$-graph $G_{n,m}$ for split reliability, that is, a connected graph with $n$ vertices and $m$ edges for which for any other such graph $H$, the split reliability of $G_{n,m}$ is at least as large as that of $H$, for {em all} values of $pin[0,1]$. Unlike the similar problems for all-terminal and two-terminal reliability, where only partial results are known, we completely solve the issue for split reliability, where we show that there is an optimal $(n,m)$-graph for split reliability if and only if $nleq3$, $m=n-1$, or $n=m=4$.

Recommendations

• Nonexistence of optimal graphs for all terminal reliability
• Optimally Reliable Graphs for Both Vertex and Edge Failures
• On the existence of uniformly optimally reliable networks
• scientific article; zbMATH DE number 1444280
• Optimally reliable networks

Cites work

• Nonexistence of optimal graphs for all terminal reliability
• On the roots of all-terminal reliability polynomials
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• Uniformly optimally reliable graphs

Cited in

(6)

• Accessibility and reliability for connected bipartite graphs
• Characterization of locally most split reliable graphs
• scientific article; zbMATH DE number 1337741 (Why is no real title available?)
• Reliability analysis of godan graphs
• Reliabilities for two kinds of graphs with smaller diameters
• Node partition formula for directed graph reliability

This page was built for publication: On the split reliability of graphs

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