Induced forests and trees in Erdős-Rényi random graph (Q6575360)

The paper studies induced forests and trees in Erdős-Rényi random graphs. In the \(G(n,p)\) model, let \(p\) be a constant and \(q=(1-p)^{-1}\). For any fixed \(\Delta\ge3\), it is shown that there is a constant \(1<a<e\) such that the size of the maximum induced tree with a maximum degree at most \(\Delta\) is almost surely equal to one of the two consecutive numbers, namely, \(\lceil2\log_q(anp)+1\rceil\) or \(\lceil2\log_q(anp)+2\rceil\). Under the same condition, there is a constant \(1<a<e\) such that the size of the maximum induced forest with a maximum degree at most \(\Delta\) is almost surely equal to \(\lceil2\log_q(anp)+1\rceil\) or \(\lceil2\log_q(anp)+2\rceil\).