Crossing properties of graph reliability functions

Abstract

We consider undirected graphs, and assume that each edge of G exists with probability p 2 (0; 1). The all{terminal reliability function A(G; p) of such a random graph G is the probability that the spanning subgraph formed by the existing edges is connected. A two{graph is a graph with two distinguished vertices called terminals. The two{terminal reliability function T (G; p) of a two{graph G is the probability that the subgraph of G induced by the existing edges contains a path connecting the terminals. Till recently no examples of pairs of graphs have been known whose all{terminal or two{terminal reliabilities cross more than twice and only one example of exactly two crossings. In [9] we proved that for every integer N there exist pairs of graphs (two{graphs) whose all{terminal (respectively, two{terminal) reliabilities cross more than N times. In this paper we give simple constructions that provide, for every sequence (m1; : : : ;mk) of natural numbers, in nitely many pairs of graphs (two{graphs) (G1; G2) of the same size such that A(G1; p) A(G2; p) (respectively, (T (G1; p T (G2; p)) have exactly k roots x1 < : : : < xk in (0; 1) such that xi is of multiplicity mi, i = 1; : : : ; k. These results are based on so called A{ and T{multiplying constructions that are interesting in themselves.

Topics

    0 Figures and Tables

      Download Full PDF Version (Non-Commercial Use)