betaFeedback

WorksMathematics

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,mT_{n,m} be the class consisting of all non-isomorphic two-terminal graphs on nn vertices and mm edges. Let GG be any two-terminal graph in Tn,mT_{n,m}, and let dd be any positive integer. For every ρ∈[0,1]ρ\in [0,1], the \emph{dd-constrained two-terminal reliability of GG at ρρ}, denoted RGd(ρ)R_G^d(ρ), is the probability that GG has some path of length at most dd joining its terminals after each of its edges is independently deleted with probability ρρ. We say GG is a \emph{dd-uniformly most reliable two-terminal graph} (dd-UMRTTG) if for each HH in Tn,mT_{n,m} and every ρ∈[0,1]ρ\in [0,1] it holds that RGd(ρ)≥RHd(ρ)R_{G}^d(ρ)\geq R_{H}^{d}(ρ). Previous works studied the existence of dd-UMRTTG in Tn,mT_{n,m} when dd is greater than or equal to n−1n-1, or equivalently, when the distance constraint is dropped. In this work, a characterization of all 11-UMRTTGs and 22-UMRTTGs is given. Several structural properties of 3-UMRTTGs are established. For every d≥3d\geq 3, we prove the existence of a unique dd-UMRTTG in Tn,(n2)−1T_{n,\binom{n}{2}-1}. In contrast, for every d≥4d\geq 4 and every n≥11n\geq 11, no dd-UMRTTG exists in Tn,mT_{n,m} whenever 20≤m≤3n−920\leq m\leq 3n-9 or 3n−5≤m≤(n2)−23n-5\leq m\leq \binom{n}{2}-2. Additionally, for each d≥5d\geq 5, it is proved that no dd-UMRTTG exists in Tn,mT_{n,m} when n≥11n\geq 11 and m=3n−8m=3n-8.

Paper details

vlnc:W_nykrxgwa
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 8

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…