Upper bounds on all-terminal reliability polynomials in terms of cycle basis lengths
Source: arxiv.org/abs/2611.12302
Let $G=(V(G),E(G))$ be a connected multigraph with $n$ vertices and $m$ edges. The all-terminal reliability polynomial of $G$ can be written as $R_G(q)=(1-q)^{n-1}\sum\limits_{i=0}^{d}H_iq^i$ where $d=m-n+1$ is the cycle rank, each edge fails independently with probability $q\in[0,1]$, and $H_0,\ldots,H_d$ are the associated coefficients. A cycle basis, which consists of cycles that form a basis of the cycle space of a graph, is an important tool for characterizing its cycle structure. The structural properties of cycle bases, together with the associated length optimization problems and…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.12302
curl -X POST /api/v1/records/arxiv/2611.12302/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.12302/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'