On some properties of random graphs of a special type

Бесплатный доступ

In this paper, we consider random subgraphs of a complete distance graph. The graph vertices are vectors x ¡ {0, 1}n satisfying the condition ǁxǁ=√n/2. The graph edges are those pairs of vectors whose elements are √n/2 apart. The threshold probability is earlier known for the property of connectivity of such random graphs. Also the threshold probability is known for the emergence of a giant component. We now prove that, as in the classical Erdos-Renyi model, the phase transition from the connectivity to its absence coincides with the transition from connectivity to the presence of isolated vertices. Also, we give a result on the limit probability of connectivity assuming that the edge probability is "inside" the phase transition.

Еще

Random graph, connectivity, isolated vertex, giant component, distance graph, threshold probability

Короткий адрес: https://sciup.org/142186200

IDR: 142186200

Статья научная