On some properties of random graphs of a special type
Автор: Yarmukhametov A.R.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Случайные графы
Статья в выпуске: 1 (13) т.4, 2012 года.
Бесплатный доступ
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