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 条
  • [31] Steiner diameter, maximum degree and size of a graph
    Mao, Yaping
    Dankelmann, Peter
    Wang, Zhao
    DISCRETE MATHEMATICS, 2021, 344 (08)
  • [32] MAXIMUM SIZE OF AN INDEPENDENT SET IN A NONPLANAR GRAPH
    ALBERTSON, MO
    HUTCHINSON, JP
    BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1975, 81 (03) : 554 - 555
  • [33] The Maximum Number of Stars in a Graph Without Linear Forest
    Sumin Huang
    Jianguo Qian
    Graphs and Combinatorics, 2022, 38
  • [34] The Maximum Number of Stars in a Graph Without Linear Forest
    Huang, Sumin
    Qian, Jianguo
    GRAPHS AND COMBINATORICS, 2022, 38 (06)
  • [35] Finding a maximum independent set in a sparse random graph
    Feige, Uriel
    Ofek, Eran
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2008, 22 (02) : 693 - 718
  • [36] The distribution of the maximum number of common neighbors in the random graph
    Rodionov, I. V.
    Zhukovskii, M. E.
    EUROPEAN JOURNAL OF COMBINATORICS, 2023, 107
  • [37] On the maximal size of tree in a random forest
    Pavlov, Yuriy L.
    DISCRETE MATHEMATICS AND APPLICATIONS, 2024, 34 (04): : 221 - 232
  • [38] Finding a maximum independent set in a sparse random graph
    Feige, U
    Ofek, E
    APPROXIMATION, RANDOMIZATION AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES, 2005, 3624 : 282 - 293
  • [39] Moment-Based Parameter Estimation in Binomial Random Intersection Graph Models
    Karjalainen, Joona
    Leskela, Lasse
    ALGORITHMS AND MODELS FOR THE WEB GRAPH, WAW 2017, 2017, 10519 : 1 - 15
  • [40] Size of the giant component in a random geometric graph
    Ganesan, Ghurumuruhan
    ANNALES DE L INSTITUT HENRI POINCARE-PROBABILITES ET STATISTIQUES, 2013, 49 (04): : 1130 - 1140