pipette
ENEnglish

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

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

Preprint

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.