Premium
Crossing properties of graph reliability functions
Author(s) -
Kelmans Alexander K.
Publication year - 2000
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/1097-0118(200011)35:3<206::aid-jgt6>3.0.co;2-7
Subject(s) - mathematics , combinatorics , discrete mathematics , graph , random graph , path (computing) , multiplicity (mathematics) , mathematical analysis , computer science , programming language
Let G be a graph and p ϵ (0, 1). Let A ( G, p ) denote the probability that if each edge of G is selected at random with probability p then the resulting spanning subgraph of G is connected. Then A ( G, p ) is a polynomial in p . We prove that for every integer k ≥ 1 and every k ‐tuple ( m 1 , m 2 , … , m k ) of positive integers there exist infinitely many pairs of graphs G 1 and G 2 of the same size such that the polynomial A ( G 1 , p ) − A ( G 2 , p ) has exactly k roots x 1 < x 2 < ··· < x k in (0, 1) such that the multiplicity of x i is m i . We also prove the same result for the two‐terminal reliability polynomial, defined as the probability that the random subgraph as above includes a path connecting two specified vertices. These results are based on so‐called A ‐ and T‐multiplying constructions that are interesting in themselves. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 206–221, 2000