Maximal induces trees in sparse random graphs (Q1121286)

The authors have studied the orders of maximal induced trees in a random graph \(G_ p\) with small edge probability p and have shown that the giant component of almost every \(G_ p\), where \(p=c/n\) and \(c>1\) is a constant, contains only some maximal trees of small orders and some very large maximal trees. The authors have presented an elementary simpler proof of a conjecture raised by P. Erdős and Z. Palka that almost every \(G_ p\) with \(p=c/n\), \(c>1\) has an induced tree on \(\Phi\) (c)n vertices where \(\Phi (c)>0\) is a function on c. In the case when \(c>1\) is small, their result is weaker than the ones proved by W. Fernandez de la Vega. The readers can find in the book `Random graphs' by B. Bollobás, a wide variety of results relating to possible orders of isolated trees in such a random graph.