# Item

ITEM ACTIONSEXPORT

Released

Report

#### On the probability of rendezvous in graphs

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

2003-1-006

(Any fulltext), 10KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Dietzfelbinger, M., & Tamaki, H.(2003). *On the probability
of rendezvous in graphs* (MPI-I-2003-1-006). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-6B83-7

##### Abstract

In a simple graph $G$ without isolated nodes the
following random experiment is carried out:
each node chooses one
of its neighbors uniformly at random.
We say a rendezvous occurs
if there are adjacent nodes $u$ and $v$
such that $u$ chooses $v$
and $v$ chooses $u$;
the probability that this happens is denoted by $s(G)$.
M{\'e}tivier \emph{et al.} (2000) asked
whether it is true
that $s(G)\ge s(K_n)$
for all $n$-node graphs $G$,
where $K_n$ is the complete graph on $n$ nodes.
We show that this is the case.
Moreover, we show that evaluating $s(G)$
for a given graph $G$ is a \numberP-complete problem,
even if only $d$-regular graphs are considered,
for any $d\ge5$.