|
On embedding random graphs into distance graphs and graphs of diameters in Euclidean spaces
A. V. Krota, A. M. Raigorodskiib a Moscow Institute of Physics and Technology
b Lomonosov Moscow State University
Abstract:
In this paper we consider the problem of finding the probability threshold for the realization of a random graph by geometric graphs in the space ${\mathbb R}^d$. In the case of graphs of diameters we prove asymptotic behavior for the threshold probability on the plane, as well as the exact expression in the case $d \ge 3$.
Bibliography: 18 titles.
Keywords:
distance graph, diameter graph, random graph.
Received: 30.04.2015
Citation:
A. V. Krot, A. M. Raigorodskii, “On embedding random graphs into distance graphs and graphs of diameters in Euclidean spaces”, Chebyshevskii Sb., 16:2 (2015), 133–143
Linking options:
https://www.mathnet.ru/eng/cheb394 https://www.mathnet.ru/eng/cheb/v16/i2/p133
|
Statistics & downloads: |
Abstract page: | 629 | Full-text PDF : | 286 | References: | 68 |
|