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 条
  • [41] A Degree Sum Condition Concerning the Connectivity and the Independence Number of a Graph
    Ozeki, Kenta
    Yamashita, Tomoki
    GRAPHS AND COMBINATORICS, 2008, 24 (05) : 469 - 483
  • [42] Connectivity, diameter, independence number and the distance spectral radius of graphs
    Zhang, Minjie
    Li, Shuchao
    Gutman, Ivan
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2017, 529 : 30 - 50
  • [43] On the Independence Number of the Generalized Petersen Graph P (n, k)
    Xu, Lian-Cheng
    Yang, Yuan-Sheng
    Xia, Zun-Quan
    Tian, Jing-Xi
    OPERATIONS RESEARCH AND ITS APPLICATIONS, PROCEEDINGS, 2009, 10 : 40 - +
  • [44] On the number of edges in induced subgraphs of a special distance graph
    Pushnyakov, F. A.
    MATHEMATICAL NOTES, 2016, 99 (3-4) : 545 - 551
  • [45] On the number of edges in induced subgraphs of a special distance graph
    F. A. Pushnyakov
    Mathematical Notes, 2016, 99 : 545 - 551
  • [46] Clique immersions in graphs of independence number two with certain forbidden subgraphs
    Quiroz, Daniel A.
    DISCRETE MATHEMATICS, 2021, 344 (06)
  • [47] The relation between the H-rank of a mixed graph and the independence number of its underlying graph
    Li, Shuchao
    Zhang, Siqi
    Xu, Baogen
    LINEAR & MULTILINEAR ALGEBRA, 2019, 67 (11) : 2230 - 2245
  • [48] Relation between the skew-rank of an oriented graph and the independence number of its underlying graph
    Jing Huang
    Shuchao Li
    Hua Wang
    Journal of Combinatorial Optimization, 2018, 36 : 65 - 80
  • [49] Bounds for the rank of a complex unit gain graph in terms of the independence number
    He, Shengjie
    Hao, Rong-Xia
    Yu, Aimei
    LINEAR & MULTILINEAR ALGEBRA, 2022, 70 (07) : 1382 - 1402
  • [50] Relation between the skew-rank of an oriented graph and the independence number of its underlying graph
    Huang, Jing
    Li, Shuchao
    Wang, Hua
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2018, 36 (01) : 65 - 80
12345