05706693

j

1196.60019 Devroye, Luc Gudmundsson, Joachim Morin, Pat On the expected maximum degree of Gabriel and Yao graphs. Adv. Appl. Probab. 41, No. 4, 1123-1140 (2009). 2009 Applied Probability Trust, Sheffield EN 60D05 68U05 52C99 random geometric graph Gabriel graph Yao graph maximum degree

doi:10.1239/aap/1261669589

Summary: Motivated by applications of Gabriel graphs and Yao graphs in wireless ad-hoc networks, we show that the maximum degree of a random Gabriel graph or Yao graph defined on $n$ points drawn uniformly at random from a unit square grows as $\Theta ( \log n / \log \log n)$ in probability.