# MPI-I-2003-1-006

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

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

| 387 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: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2003-1-006

**BibTeX**
`@TECHREPORT{``HisaoDietzfelbinger2003``,`

` 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},`

`}`