## DIMACS TR: 98-39

## Crossing Properties of Graph Reliability Functions

### Author: Alexander K. Kelmans

**
ABSTRACT
**

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