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 .