b'@techreport{MPI-I-94-224,'b'\nTITLE = {On the probability of rendezvous in graphs},\nAUTHOR = {Dietzfelbinger, Martin and Tamaki, Hisao},\nLANGUAGE = {eng},\nNUMBER = {MPI-I-2003-1-006},\nINSTITUTION = {Max-Planck-Institut f{\\"u}r Informatik},\nADDRESS = {Saarbr{\\"u}cken},\nYEAR = {2003},\nDATE = {2003},\nABSTRACT = {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$.},\nTYPE = {Research Report / Max-Planck-Institut f\xc3\xbcr Informatik},\n}\n'