Random perturbation of sparse graphs
arXiv preprint arXiv:2004.04672, 2020•arxiv.org
In the model of randomly perturbed graphs we consider the union of a deterministic graph
$\mathcal {G} _\alpha $ with minimum degree $\alpha n $ and the binomial random graph
$\mathbb {G}(n, p) $. This model was introduced by Bohman, Frieze, and Martin and for
Hamilton cycles their result bridges the gap between Dirac's theorem and the results by
Pos\'{a} and Kor\v {s} unov on the threshold in $\mathbb {G}(n, p) $. In this note we extend
this result in $\mathcal {G} _\alpha\cup\mathbb {G}(n, p) $ to sparser graphs with $\alpha= o …
$\mathcal {G} _\alpha $ with minimum degree $\alpha n $ and the binomial random graph
$\mathbb {G}(n, p) $. This model was introduced by Bohman, Frieze, and Martin and for
Hamilton cycles their result bridges the gap between Dirac's theorem and the results by
Pos\'{a} and Kor\v {s} unov on the threshold in $\mathbb {G}(n, p) $. In this note we extend
this result in $\mathcal {G} _\alpha\cup\mathbb {G}(n, p) $ to sparser graphs with $\alpha= o …
In the model of randomly perturbed graphs we consider the union of a deterministic graph with minimum degree and the binomial random graph . This model was introduced by Bohman, Frieze, and Martin and for Hamilton cycles their result bridges the gap between Dirac's theorem and the results by Pos\'{a} and Kor\v{s}unov on the threshold in . In this note we extend this result in to sparser graphs with . More precisely, for any and we show that a.a.s. is Hamiltonian, where . If is a fixed constant this gives the aforementioned result by Bohman, Frieze, and Martin and if the random part is sufficient for a Hamilton cycle. We also discuss embeddings of bounded degree trees and other spanning structures in this model, which lead to interesting questions on almost spanning embeddings into .
arxiv.org
以上显示的是最相近的搜索结果。 查看全部搜索结果