{"id":"arxiv/2611.12302","url":"https://arxiv.org/abs/2611.12302","tags":["math.CO"],"score":0,"title":"Upper bounds on all-terminal reliability polynomials in terms of cycle basis lengths","domain":"math.CO","source":"arxiv","authors":["Tingzeng Wu","Xueqing Li","Jianxuan Luo","Hong-Jian Lai"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-09","reactions":{}}