Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.16514 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912595722633216 |
|---|---|
| author | Romero, Pablo |
| author_facet | Romero, Pablo |
| contents | A two-terminal graph is a graph G equipped with two vertices in V(G) called terminals. Let T(n,m) be the set of two-terminal graphs on n vertices and m edges. Let G be in T(n,m) and let p be in [0,1]. The two-terminal reliability of G at p, denoted R_G(p), is the probability that G has a path joining its terminals after each of its edges is independently removed with probability 1 - p. We say G is a locally most reliable two-terminal graph (LMRTTG) if for each H in T(n,m) there exists a positive real number delta such that for every p in (0, delta) it holds that R_G(p) >= R_H(p).
It is simple to prove that there exists a unique LMRTTG in T(n,m) when n >= 4 and 5 <= m <= 2n - 3. Gong and Lin [Discrete Appl. Math. 356 (2024), 393-402] further proved that there exists a unique LMRTTG in T(n,m) when n >= 6 and 2n - 3 <= m <= n(n - 1)/2, except for some pairs of integers n and m which satisfy that n >= 6 and (1/2)(n - 2)(n - 3) - (n - 2)/2 <= m - (2n - 3) <= (1/2)(n - 2)(n - 3) + (n - 2)/2. All cases unresolved in earlier works are covered here. In this article it is proved that in each set T(n,m) such that n >= 4 and 5 <= m <= n(n - 1)/2 there exists a unique LMRTTG, called G(n,m). A construction of G(n,m) is also given. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_16514 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Existence, uniqueness and construction of locally most reliable two-terminal graphs Romero, Pablo Combinatorics 05C31 A two-terminal graph is a graph G equipped with two vertices in V(G) called terminals. Let T(n,m) be the set of two-terminal graphs on n vertices and m edges. Let G be in T(n,m) and let p be in [0,1]. The two-terminal reliability of G at p, denoted R_G(p), is the probability that G has a path joining its terminals after each of its edges is independently removed with probability 1 - p. We say G is a locally most reliable two-terminal graph (LMRTTG) if for each H in T(n,m) there exists a positive real number delta such that for every p in (0, delta) it holds that R_G(p) >= R_H(p). It is simple to prove that there exists a unique LMRTTG in T(n,m) when n >= 4 and 5 <= m <= 2n - 3. Gong and Lin [Discrete Appl. Math. 356 (2024), 393-402] further proved that there exists a unique LMRTTG in T(n,m) when n >= 6 and 2n - 3 <= m <= n(n - 1)/2, except for some pairs of integers n and m which satisfy that n >= 6 and (1/2)(n - 2)(n - 3) - (n - 2)/2 <= m - (2n - 3) <= (1/2)(n - 2)(n - 3) + (n - 2)/2. All cases unresolved in earlier works are covered here. In this article it is proved that in each set T(n,m) such that n >= 4 and 5 <= m <= n(n - 1)/2 there exists a unique LMRTTG, called G(n,m). A construction of G(n,m) is also given. |
| title | Existence, uniqueness and construction of locally most reliable two-terminal graphs |
| topic | Combinatorics 05C31 |
| url | https://arxiv.org/abs/2509.16514 |