Portal de Periódicos da CAPES

On the order of the largest induced tree in a random graph

1986; Elsevier BV; Volume: 15; Issue: 1 Linguagem: Inglês

10.1016/0166-218x(86)90021-1

1872-6771

Zbigniew Pałka, Andrzej Ruciński,

Computational Geometry and Mesh Generation

Consider a random graph K ( n , p ) with n labeled vertices in which the edges are chosen independently and with a probability p . Let T n ( p ) be the order of the largest induced tree in K ( n , p ). Among other results it is shown, using an algorithmic approach, that if p =( c log n )/ n , where c ≥ e is a constant, then for any fixed ε > 0 1 c −ε log log n log n n<T n (p)< 2 c +ε log log n log n almost surely.