Premium
The largest induced tree in a sparse random graph
Author(s) -
de la Vega W. Fernandez
Publication year - 1996
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199608/09)9:1/2<93::aid-rsa6>3.0.co;2-6
Subject(s) - combinatorics , mathematics , random graph , graph , tree (set theory) , binary logarithm , discrete mathematics , random tree , frieze , computer science , motion planning , artificial intelligence , robot , archaeology , history
The author proved that, for c > 1, the random graph G ( n, p ) on n vertices with edge probability p = c/n contains almost always an induced tree on at least α c n (1 − o (1)) vertices, where α c is the positive root of the equation c α = log(1 + c 2 α). It is shown here that if c is sufficiently large, then the largest size of an induced tree in G ( n, p ), p = c/n , is almost always at least 2 n / c (log c − log log c − 1). The proof relies heavily on a theorem of Frieze concerning the independence number of a sparse random graph. © 1996 John Wiley & Sons, Inc.