Universality for bounded degree spanning trees in randomly perturbed graphs

Authors:

Abstract
We solve a problem of Krivelevich, Kwan and Sudakov concerning the threshold for the containment of all bounded degree spanning trees in the model of randomly perturbed dense graphs. More precisely, we show that, if we start with a dense graph Gα on n vertices with δ(Gα) ≥ αn for α > 0 and we add to it the binomial random graph G(n,C/n), then with high probability the graph Gα∪G(n,C/n) contains copies of all spanning trees with maximum degree at most Δ simultaneously, where C depends only on α and Δ.
Funding Information
  • EPSRC (EP/R00532X/1)
  • FAPESP (2014/18641‐5, 2013/03447‐6, 2013/03447‐6)
  • CNPq (310974/2013‐5, 311412/2018‐1, 459335/2014‐6)
  • DFG (PE 2299/1‐1)
  • CAPES (430/15, 57350402)
  • DAAD (57391197)

This publication has 15 references indexed in Scilit: