MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments


On the probability of rendezvous in graphs

Dietzfelbinger, Martin and Tamaki, Hisao

March 2003, 30 pages.

Status: available - back from printing

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$.

  • Attachement: (387 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Dietzfelbinger, Martin and Tamaki, Hisao},
  TITLE = {On the probability of rendezvous in graphs},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-2003-1-006},
  MONTH = {March},
  YEAR = {2003},
  ISSN = {0946-011X},