Paperlane

no. 12 · Tuesday 10 November 2026

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

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

math.CO

Abstract

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 construction algorithms, have been extensively studied. In this context, Colbourn posed the following open problem, which concerns upper bounds on the reliability coefficients in terms of cycle-basis lengths: For all-terminal reliability, is it true that if $G$ has a cycle basis containing cycles of lengths $c_1,\ldots,\allowbreak c_{m-n+1}$, then $H_i \le\sum\limits_{\substack{I\subseteq\{1,\ldots,m-n+1\},|I|=i}}\prod\limits_{j\in I}(c_j-1)$? In this paper, we establish a result that resolves this open problem.

fields
Combinatorics
pdf ↗ page arXiv:2611.12302 ↗