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