On the probability of rendezvous in graphs

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étivier, Saheb, and Zemmari [“Randomized rendezvous,” Algorithms, trees, combinatorics, and probabilities, Eds. G. Gardy and A. Mokkadem, Trends in Mathematics, 183–194. Birkhäuser, Boston, 2000.] asked whether it is true that s ( G ) ≥ 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 #P‐complete problem, even if only d ‐regular graphs are considered, for any d ≥ 5. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2005