On the probability of rendezvous in graphs
Martin Dietzfelbinger, Hisao Tamaki · Random Structures and Algorithms · 2004
Abstract 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(Kn) for all n‐node graphs G, where Kn 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