Connections in Randomly Oriented Graphs

Abstract: Given an undirected graph

G

, let us randomly orient

G

by tossing independent (possibly biased) coins, one for each edge of

G

. Writing

a i g h t a r r o w b

for the event that there exists a directed path from a vertex

a

to a vertex

b

in such a random orientation, we prove that

m a t h b b P (s i g h t a r r o w a c a p s i g h t a r r o w b) g e m a t h b b P (s i g h t a r r o w a) m a t h b b P (s i g h t a r r o w b)

for any three vertices

s

,

a

and

b

of

G

.

Cites Work

Cited In (4)

This page was built for publication: Connections in Randomly Oriented Graphs