Spanning trees in randomly perturbed graphs

Cited 5 time in webofscience Cited 0 time in scopus
  • Hit : 217
  • Download : 0
A classical result of Komlos, Sarkozy, and Szemeredi states that every n-vertex graph with minimum degree at least (1/2 + o(1))n contains every n-vertex tree with maximum degree O(n/logn). Krivelevich, Kwan, and Sudakov proved that for every n-vertex graph G(alpha) with minimum degree at least alpha n for any fixed alpha > 0 and every n-vertex tree T with bounded maximum degree, one can still find a copy of T in G(alpha) with high probability after adding O(n) randomly chosen edges to G(alpha). We extend the latter results to trees with (essentially) unbounded maximum degree; for a given no(1)<=Delta <= cn/logn and alpha > 0, we determine up to a constant factor the number of random edges that we need to add to an arbitrary n-vertex graph with minimum degree alpha n in order to guarantee with high probability a copy of any fixed n-vertex tree with maximum degree at most Delta.
Publisher
WILEY
Issue Date
2020-01
Language
English
Article Type
Article
Citation

RANDOM STRUCTURES &amp; ALGORITHMS, v.56, no.1, pp.169 - 219

ISSN
1042-9832
DOI
10.1002/rsa.20886
URI
http://hdl.handle.net/10203/270072
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 5 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0