Upper bounds on all-terminal reliability polynomials in terms of cycle basis lengths
En palabras de los autores
Let be a connected multigraph with vertices and edges. The all-terminal reliability polynomial of can be written as where is the cycle rank, each edge fails independently with probability , and 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 has a cycle basis containing cycles of lengths , then ? In this paper, we establish a result that resolves this open problem.
Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.