Mathematics – Combinatorics
Scientific paper
1998-02-09
Mathematics
Combinatorics
21 pages
Scientific paper
For a finite multigraph G, the reliability function of G is the probability R_G(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 R_G(q)=0 then |q|<=1. We verify that this conjectured property of R_G(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.
No associations
LandOfFree
Zeros of reliability polynomials and f-vectors of matroids does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Zeros of reliability polynomials and f-vectors of matroids, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Zeros of reliability polynomials and f-vectors of matroids will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-263958