The maximum size of an induced forest in the binomial random graph

被引:0
|
作者
Akhmejanova, Margarita [1 ]
Kozhevnikov, Vladislav [2 ]
机构
[1] King Abdullah Univ Sci & Technol KAUST, Comp Elect & Math Sci & Engn Div, Thuwal 239556900, Saudi Arabia
[2] Moscow Inst Phys & Technol, Lab Combinatorial & Geometr Struct, Dolgoprudnyi, Russia
基金
俄罗斯科学基金会;
关键词
Random graph; Induced forest; Frieze; G(n; p); Induced graph; Maximum induced forest; LARGEST INDUCED TREE;
D O I
10.1016/j.disc.2024.114030
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
The celebrated Frieze's result about the independence number of G ( n , p ) states that it is concentrated in an interval of size o ( 1 / p ) for all C- epsilon / n < p = o ( 1 ) . We show concentration in an interval of size o ( 1 / p ) for the maximum size (number of vertices) of an induced forest in G ( n , p ) for all C- epsilon / n < p < 1 - epsilon . Presumably, it is the first generalization of Frieze's result to another class of induced subgraphs for such a range of p .
引用
收藏
页数:11
相关论文
共 50 条
  • [41] Maximum Size of a Graph with Given Fractional Matching Number
    Ma, Tianlong
    Qian, Jianguo
    Shi, Chao
    ELECTRONIC JOURNAL OF COMBINATORICS, 2022, 29 (03):
  • [42] ON MAXIMUM WEIGHT OF A BIPARTITE GRAPH OF GIVEN ORDER AND SIZE
    Hornak, Mirko
    Jendrol', Stanislav
    Schiermeyer, Ingo
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2013, 33 (01) : 147 - 165
  • [43] Maximum size of a connected graph with given domination parameters
    Arumugam, S
    Velammal, S
    ARS COMBINATORIA, 1999, 52 : 221 - 227
  • [44] The maximum size of a nonhamiltonian graph with given order and connectivity
    Zhan, Xingzhi
    Zhang, Leilei
    DISCRETE MATHEMATICS, 2023, 346 (01)
  • [45] On the maximum weight of a planar graph of given order and size
    Gajdos, Andrej
    Hornak, Mirko
    Hudak, Peter
    Madaras, Toma
    DISCRETE APPLIED MATHEMATICS, 2014, 177 : 101 - 110
  • [46] The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum Degree
    Cutler, Jonathan
    Radcliffe, A. J.
    JOURNAL OF GRAPH THEORY, 2017, 84 (02) : 134 - 145
  • [47] Random projection forest initialization for graph convolutional networks
    Alshammari, Mashaan
    Stavrakakis, John
    Ahmed, Adel F.
    Takatsuka, Masahiro
    METHODSX, 2023, 11
  • [48] Average Distance and Maximum Induced Forest
    Hansen, Pierre
    Hertz, Alain
    Kilani, Rim
    Marcotte, Odile
    Schindl, David
    JOURNAL OF GRAPH THEORY, 2009, 60 (01) : 31 - 54
  • [49] On the maximum total sample size of a group sequential test about binomial proportions
    Kepner, JL
    Chang, MN
    STATISTICS & PROBABILITY LETTERS, 2003, 62 (01) : 87 - 92
  • [50] Exact computation of Maximum Induced Forest
    Razgon, Igor
    ALGORITHM THEORY - SWAT 2006, PROCEEDINGS, 2006, 4059 : 160 - 171