Premium
Sharp threshold for the appearance of certain spanning trees in random graphs
Author(s) -
Hefetz Dan,
Krivelevich Michael,
Szabó Tibor
Publication year - 2012
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/rsa.20472
Subject(s) - combinatorics , mathematics , random graph , bounded function , degree (music) , graph , path (computing) , binomial (polynomial) , spanning tree , tree (set theory) , discrete mathematics , physics , mathematical analysis , computer science , statistics , acoustics , programming language
We prove that a given tree T on n vertices with bounded maximum degree is contained asymptotically almost surely in the binomial random graph \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}G(n,\frac{(1+\varepsilon) \log n}{n})\end{align*}\end{document} provided that T belongs to one of the following two classes: (1) T has linearly many leaves; (2) T has a path of linear length all of whose vertices have degree two in T . © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012