Probl. Peredachi Inf., 2020 Volume 56, Issue 4, Pages 50–63
(Mi ppi2328)
This article is cited in
4 papers
Large Systems
On stability of the independence number of a certain distance graph
P. A. Ogarok a ,
A. M. Raigorodskii bcdeaf a Moscow Institute of Physics and Technology (State University), Moscow, Russia
b Phystech School of Applied Mathematics and Informatics,
Moscow Institute of Physics and Technology (State University), Moscow, Russia
c Institute of Mathematics and Computer Science, Buryat State University, Ulan-Ude, Russia
d Caucasus Mathematical Center, Adyghe State University, Maykop, Republic of Adygea, Russia
e Department of Mathematical Statistics and Random Processes,
Faculty of Mechanics and Mathematics,
Lomonosov Moscow State University, Moscow, Russia
f Laboratory of Advanced Combinatorics and Network Applications,
Moscow Institute of Physics and Technology (State University), Moscow, Russia
Abstract:
We study the asymptotic behavior of the independence number of a random subgraph of a certain
$(r,s)$ -distance graph. We provide upper and lower bounds for the critical edge survival probability under which a phase transition occurs, i.e., large new independent sets appear in the subgraph, which did not exist in the original graph.
Keywords:
random graph, distance graph, independence number.
UDC:
621.391 :
519.176 Received: 09.03.2020
Revised: 29.10.2020
Accepted: 29.10.2020
DOI:
10.31857/S0555292320040051
© , 2025