DIMACS TR: 98-39

Crossing Properties of Graph Reliability Functions

Author: Alexander K. Kelmans


We consider undirected graphs, and assume that each edge of $G$ exists with probability $p \in (0,1)$. The all--terminal reliability function 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 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 [8] 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 set $\{(n_1,m_1), \ldots (n_k,m_k)\}$ of ordered pairs of integers (where all $m_i$ are distinct), a pair of graphs (two--graphs) of the same size whose all--terminal (respectively, two--terminal) reliability functions have exactly $n_1 + \ldots + n_k$ crossings and exactly $n_i$ crossings of multiplicity $m_i$ for every $i = 1, \ldots , k$.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-39.ps.gz
DIMACS Home Page