Independence numbers of random subgraphs of a distance graph

被引:0
作者
M. M. Pyaderkin
机构
[1] Lomonosov Moscow State University,
来源
Mathematical Notes | 2016年 / 99卷
关键词
distance graph; random subgraph; independence number; Erdős–Rényi model;
D O I
暂无
中图分类号
学科分类号
摘要
We consider the so-called distance graph G(n, 3, 1), whose vertices can be identified with three-element subsets of the set {1, 2,..., n}, two vertices being joined by an edge if and only if the corresponding subsets have exactly one common element. We study some properties of random subgraphs of G(n, 3, 1) in the Erdős–Rényi model, in which each edge is included in the subgraph with some given probability p independently of the other edges. We find the asymptotics of the independence number of a random subgraph of G(n, 3, 1).
引用
收藏
页码:312 / 319
页数:7
相关论文
共 50 条
  • [1] Independence numbers of random subgraphs of a distance graph
    Pyaderkin, M. M.
    MATHEMATICAL NOTES, 2016, 99 (1-2) : 312 - 319
  • [2] Independence numbers of random subgraphs of distance graphs
    M. M. Pyaderkin
    Mathematical Notes, 2016, 99 : 556 - 563
  • [3] Independence numbers of random subgraphs of distance graphs
    Pyaderkin, M. M.
    MATHEMATICAL NOTES, 2016, 99 (3-4) : 556 - 563
  • [4] Independence numbers and chromatic numbers of the random subgraphs of some distance graphs
    Bogolubsky, L. I.
    Gusev, A. S.
    Pyaderkin, M. M.
    Raigorodskii, A. M.
    SBORNIK MATHEMATICS, 2015, 206 (10) : 1340 - 1374
  • [5] Small subgraphs and their extensions in a random distance graph
    Burkin, A. V.
    Zhukovskii, M. E.
    SBORNIK MATHEMATICS, 2018, 209 (02) : 163 - 186
  • [6] SMALL SUBGRAPHS IN RANDOM DISTANCE GRAPHS
    Burkin, A. V.
    THEORY OF PROBABILITY AND ITS APPLICATIONS, 2016, 60 (03) : 367 - 382
  • [7] On Stability of the Independence Number of a Certain Distance Graph
    Ogarok, P. A.
    Raigorodskii, A. M.
    PROBLEMS OF INFORMATION TRANSMISSION, 2020, 56 (04) : 345 - 357
  • [8] On Stability of the Independence Number of a Certain Distance Graph
    P. A. Ogarok
    A. M. Raigorodskii
    Problems of Information Transmission, 2020, 56 : 345 - 357
  • [9] On local and global independence numbers of a graph
    Faudree, RJ
    Ryjácek, Z
    Schelp, RH
    DISCRETE APPLIED MATHEMATICS, 2003, 132 (1-3) : 79 - 84
  • [10] 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