Characterization of locally most split reliable graphs
Author:
Preprint
Abstract
A two-terminal graph is a graph equipped with two distinguished vertices, called terminals. Let $T_{n,m}$ be the set of all nonisomorphic connected simple two-terminal graphs on $n$ vertices and $m$ edges. Let $G$ be any two-terminal graph in $T_{n,m}$. For every number $p$ in $[0,1]$ we let each of the edges in $G$ be independently deleted with probability $1-p$. The split reliability $SR_{G}(p)$ is the probability that the resulting spanning subgraph has precisely $2$ connected components, each one including one terminal. The two-terminal graph $G$ is uniformly most split reliable if $SR_G(p)\geq SR_{H}(p)$ for each $H$ in $T_{n,m}$ and every $p$ in $[0,1]$. We say $G$ is locally most split reliable if there exists $δ>0$ such that $SR_G(p)\geq SR_{H}(p)$ for each $H$ in $T_{n,m}$ and every $p$ in $(1-δ,1)$. Brown and McMullin showed that there exists uniformly most split reliable graphs in each class $T_{n,m}$ such that $m=n-1$, $m=\binom{n}{2}$, or $m=\binom{n}{2}-1$. The authors also proved that there is no uniformly most split reliable two-terminal graph in $T_{n,n}$ when $n\geq 6$ and specified in which classes $T_{n,m}$ such that $n\leq 7$ there exist uniformly most split reliable graphs. The existence or nonexistence of uniformly most split reliable graphs in the remaining cases is posed by Brown and McMullin as an open problem. In this work, the set $\mathcal{G}_{n,m}$ consisting of all locally most split reliable graphs is characterized in each nonempty class $T_{n,m}$. It is proved that a graph in $T_{n,m}$ is locally most split reliable if and only if its split reliability equals that of the balloon graph equipped with two terminals whose distance equals its diameter. Finally, it is proved that there is no uniformly most split reliable graph in $T_{n,m}$ when $n\geq 7$ and $n\leq m \leq \binom{n-3}{2}+3$.
Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- On the construction of locally most reliable two-terminal graphsDiscrete Applied Mathematics, 2024
- On maximum graphs in Tutte polynomial posetsDiscrete Applied Mathematics, 2023
- On the split reliability of graphsNetworks, 2023
- Extremal graphs for the Tutte polynomialJournal of Combinatorial Theory, Series B, 2022
- Uniformly optimally reliable graphs: A surveyNetworks, 2021
- On uniformly most reliable two‐terminal graphsNetworks, 2018
- On the roots of all-terminal reliability polynomialsDiscrete Mathematics, 2017
- Undirected simple connected graphs with minimum number of spanning treesDiscrete Mathematics, 2009
- The Brown–Colbourn conjecture on zeros of reliability polynomials is falseJournal of Combinatorial Theory, Series B, 2004
- Reliable circuits using less reliable relaysJournal of the Franklin Institute, 1956