Delphi.science

Upper bounds on all-terminal reliability polynomials in terms of cycle basis lengths

Source: arxiv.org/abs/2611.12302

Tingzeng Wu, Xueqing Li, Jianxuan Luo, Hong-Jian Lai

arXivarxiv/2611.12302Nov 9, 2026math.COscore 0

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…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

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}'