Existence of most reliable two-terminal graphs with distance constraints
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915263309414400 |
|---|---|
| author | Romero, Pablo |
| author_facet | Romero, Pablo |
| contents | 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 nonisomorphic 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 each $ρ\in [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 $ρ\in [0,1]$ it holds that $R_{G}^d(ρ)\geq 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. Then, it is proved that there exists a unique $3$-UMRTTG in $T_{n,m}$ when $n\geq 6$ and $5 \leq m \leq 2n-3$. Finally, for each $d\geq 4$ and each $n\geq 11$ it is proved that there is no $d$-UMRTTG in $T_{n,m}$ when $20 \leq m \leq 3n-9$ or when $3n-5 \leq m \leq \binom{n}{2}-2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_19858 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Existence of most reliable two-terminal graphs with distance constraints Romero, Pablo Combinatorics 05C31 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 nonisomorphic 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 each $ρ\in [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 $ρ\in [0,1]$ it holds that $R_{G}^d(ρ)\geq 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. Then, it is proved that there exists a unique $3$-UMRTTG in $T_{n,m}$ when $n\geq 6$ and $5 \leq m \leq 2n-3$. Finally, for each $d\geq 4$ and each $n\geq 11$ it is proved that there is no $d$-UMRTTG in $T_{n,m}$ when $20 \leq m \leq 3n-9$ or when $3n-5 \leq m \leq \binom{n}{2}-2$. |
| title | Existence of most reliable two-terminal graphs with distance constraints |
| topic | Combinatorics 05C31 |
| url | https://arxiv.org/abs/2504.19858 |