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 条
  • [31] The k-Distance Independence Number and 2-Distance Chromatic Number of Cartesian Products of Cycles
    Shao, Zehui
    Vesel, Aleksander
    Xu, Jin
    BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2018, 41 (03) : 1377 - 1391
  • [32] Independence number of subspace inclusion graph and subspace sum graph of a vector space
    Ma, Xiaobin
    Wang, Dengyin
    LINEAR & MULTILINEAR ALGEBRA, 2018, 66 (12) : 2430 - 2437
  • [33] Skew-rank of an oriented graph and independence number of its underlying graph
    Li, Xueliang
    Xia, Wen
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2019, 38 (01) : 268 - 277
  • [34] Skew-rank of an oriented graph and independence number of its underlying graph
    Xueliang Li
    Wen Xia
    Journal of Combinatorial Optimization, 2019, 38 : 268 - 277
  • [35] The k-Distance Independence Number and 2-Distance Chromatic Number of Cartesian Products of Cycles
    Zehui Shao
    Aleksander Vesel
    Jin Xu
    Bulletin of the Malaysian Mathematical Sciences Society, 2018, 41 : 1377 - 1391
  • [36] On large subgraphs of a distance graph which have small chromatic number
    A. A. Kokotkin
    Mathematical Notes, 2014, 96 : 298 - 300
  • [37] On large subgraphs of a distance graph which have small chromatic number
    Kokotkin, A. A.
    MATHEMATICAL NOTES, 2014, 96 (1-2) : 298 - 300
  • [38] A new estimate for the number of edges in induced subgraphs of a special distance graph
    Ph. A. Pushnyakov
    Problems of Information Transmission, 2015, 51 : 371 - 377
  • [39] A Degree Sum Condition Concerning the Connectivity and the Independence Number of a Graph
    Kenta Ozeki
    Tomoki Yamashita
    Graphs and Combinatorics, 2008, 24 : 469 - 483
  • [40] Optimization of eigenvalue bounds for the independence and chromatic number of graph powers
    Abiad, A.
    Coutinho, G.
    Fiol, M. A.
    Nogueira, B. D.
    Zeijlemaker, S.
    DISCRETE MATHEMATICS, 2022, 345 (03)
12345