Premium
On the probability of rendezvous in graphs
Author(s) -
Dietzfelbinger Martin,
Tamaki Hisao
Publication year - 2005
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20032
Subject(s) - rendezvous , combinatorics , mathematics , random graph , struct , graph , discrete mathematics , node (physics) , random regular graph , computer science , line graph , pathwidth , physics , astronomy , quantum mechanics , spacecraft , programming language
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 ( 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