Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


On the probability of rendezvous in graphs

Dietzfelbinger, Martin and Tamaki, Hisao

MPI-I-2003-1-006. March 2003, 30 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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$.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-2003-1-006.ps387 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
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},