Existence of uniformly most reliable two-terminal graphs with distance constraints
Abstract
A two-terminal graph is a simple graph equipped with two distinguished vertices, called terminals. Let Tn,m be the class consisting of all non-isomorphic two-terminal graphs on n vertices and m edges. Let G be any two-terminal graph in Tn,m, and let d be any positive integer. For every ρ∈ [0,1], the \emph{d-constrained two-terminal reliability of G at ρ}, denoted RGd(ρ), 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 \emph{d-uniformly most reliable two-terminal graph} (d-UMRTTG) if for each H in Tn,m and every ρ∈ [0,1] it holds that RGd(ρ)≥ RHd(ρ). Previous works studied the existence of d-UMRTTG in Tn,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. Several structural properties of 3-UMRTTGs are established. For every d≥ 3, we prove the existence of a unique d-UMRTTG in Tn,binomn2−1. In contrast, for every d≥ 4 and every n≥ 11, no d-UMRTTG exists in Tn,m whenever 20≤ m≤ 3n−9 or 3n−5≤ m≤ binomn2−2. Additionally, for each d≥ 5, it is proved that no d-UMRTTG exists in Tn,m when n≥ 11 and m=3n−8.
Related
- Optimal Guidance with Terminal Intercept-Angle Constraints and Acceleration Bounds
- A computational comparison of handling distance constraints in MINLP
- Exact Second-Order Asymptotics for Covert Communication over DMCs with Variational Distance Constraints
- A Wilson group of non-uniformly exponential growth
- A remark on the compactness of manifolds with non-negative Ricci curvature and uniformly convex boundary
BibTeX
@misc{romero2026existence,
title = {{Existence of uniformly most reliable two-terminal graphs with distance constraints}},
author = {Pablo Romero},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.36120},
eprint = {2610.36120},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.36120},
}
RIS
TY - UNPB
TI - Existence of uniformly most reliable two-terminal graphs with distance constraints
AU - Pablo Romero
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.36120
UR - https://arxiv.org/abs/2610.36120
AB - 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 non-isomorphic 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 every ρ∈ [0,1], the \emph{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 \emph{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. Several structural properties of 3-UMRTTGs are established. For every d≥ 3, we prove the existence of a unique d-UMRTTG in T_n,binomn2−1. In contrast, for every d≥ 4 and every n≥ 11, no d-UMRTTG exists in T_n,m whenever 20≤ m≤ 3n−9 or 3n−5≤ m≤ binomn2−2. Additionally, for each d≥ 5, it is proved that no d-UMRTTG exists in T_n,m when n≥ 11 and m=3n−8.
ER -