1998/02/09 by David G. Wagner, Wagner, David G.
Computer Science · Mathematics · #05C99 (Primary) 26C10 #06A08 (Secondary) #95C15 #Advanced Algebra and Logic #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Commutative Algebra and Its Applications #FOS: Mathematics #math.CO #msc:05C99 #msc:06A08 #msc:26C10 #msc:95C15
paper · pdf · doi:10.48550/arxiv.math/9802047
21 pages
arxiv created 1998/02/09 · openalex publication_date 1998/02/09 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a finite multigraph G, the reliability function of G is the probability RG(q) that if each edge of G is deleted independantly with probability q then the remaining edges of G induce a connected spanning subgraph of G; this is a polynomial function of q. In 1992, Brown and Colbourn conjectured that for any connected multigraph G, if the complex number q is such that RG(q)=0 then |q|<=1. We verify that this conjectured property of RG(q) holds if G is a series-parallel network. The proof is by an application of the Hermite-Biehler Theorem and development of a theory of higher-order interlacing for polynomials with only real nonpositive zeros. We conclude by establishing some new inequalities which are satisfied by the f-vector of any matroid without coloops, and by discussing some stronger inequalities which would follow (in the cographic case) from the Brown-Colbourn Conjecture, and are hence true for cographic matroids of series-parallel networks.