On Stability of the Independence Number of a Certain Distance Graph

被引：0
作者：
P. A. Ogarok
A. M. Raigorodskii
机构：
[1] Department of Discrete Mathematics,
[2] Faculty of Innovation and High Technology,undefined
[3] Moscow Institute of Physics and Technology (State University),undefined
[4] Phystech School of Applied Mathematics and Informatics and Laboratory of Advanced Combinatorics and Network Applications,undefined
[5] Moscow Institute of Physics and Technology (State University),undefined
[6] Department of Mathematical Statistics and Random Processes,undefined
[7] Faculty of Mechanics and Mathematics,undefined
[8] Lomonosov Moscow State University,undefined
[9] Caucasus Mathematical Center,undefined
[10] Adyghe State University,undefined
[11] Institute of Mathematics and Computer Science,undefined
[12] Buryat State University,undefined
来源：
Problems of Information Transmission | 2020年 / 56卷
关键词：
random graph; distance graph; independence number;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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.
引用
收藏
页码：345 / 357
页数：12
相关论文
共 50 条
12345