Sharp threshold for the appearance of certain spanning trees in random graphs
Sharp threshold for the appearance of certain spanning trees in random graphs
复制标题
随机图中某些生成树出现的尖锐阈值
DOI：
10.1002/rsa.20472
复制
发表时间：
2012
影响因子：
1
通讯作者：
Tibor Szabó
中科院分区：
文献类型：
--
作者：
Dan Hefetz;Michael Krivelevich;Tibor Szabó
证明了给定的n个顶点上的有界最大度的树T渐近几乎必然包含在二项随机图\documentclass{article}\usepackage{mathrsfs，amsmath，amssymb}\pagestyle{empty}\开始{document}\开始{align*}G中（n，\frac{（1+\varepident）\log n}{n}）\end{align*}\end{document}假设T属于以下两类之一：（1）T有线性多个叶子;（2）T有一条线性长度的路，它的所有顶点在T中的度都是2。© 2012 Wiley Periodicals，Inc.随机结构算法，2012
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