Spanning trees in randomly perturbed graphs
A classical result of Komlós, Sárközy, and Szemerédi states that every n-vertex graph with minimum degree at least (1/2 + o(1))n contains every n-vertex tree with maximum degree . Krivelevich, Kwan, and Sudakov proved that for every n-vertex graph Gα with minimum degree at least αn for any fixed...
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Dokumenttyp: | Article (Journal) |
| Sprache: | Englisch |
| Veröffentlicht: |
2020
|
| In: |
Random structures & algorithms
Year: 2020, Jahrgang: 56, Heft: 1, Pages: 169-219 |
| ISSN: | 1098-2418 |
| DOI: | 10.1002/rsa.20886 |
| Online-Zugang: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1002/rsa.20886 Verlag, lizenzpflichtig, Volltext: https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.20886 
|
| Verfasserangaben: | Felix Joos, Jaehoon Kim |
MARC
| LEADER | 00000caa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 181059734X | ||
| 003 | DE-627 | ||
| 005 | 20220820223827.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 220715s2020 xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.1002/rsa.20886 |2 doi | |
| 035 | |a (DE-627)181059734X | ||
| 035 | |a (DE-599)KXP181059734X | ||
| 035 | |a (OCoLC)1341464039 | ||
| 040 | |a DE-627 |b ger |c DE-627 |e rda | ||
| 041 | |a eng | ||
| 084 | |a 28 |2 sdnb | ||
| 100 | 1 | |a Joos, Felix |d 1989- |e VerfasserIn |0 (DE-588)1075006171 |0 (DE-627)832846244 |0 (DE-576)442747438 |4 aut | |
| 245 | 1 | 0 | |a Spanning trees in randomly perturbed graphs |c Felix Joos, Jaehoon Kim |
| 264 | 1 | |c 2020 | |
| 300 | |a 51 | ||
| 336 | |a Text |b txt |2 rdacontent | ||
| 337 | |a Computermedien |b c |2 rdamedia | ||
| 338 | |a Online-Ressource |b cr |2 rdacarrier | ||
| 500 | |a Published on: 17 October 2019 | ||
| 500 | |a Gesehen am 15.07.2022 | ||
| 520 | |a A classical result of Komlós, Sárközy, and Szemerédi states that every n-vertex graph with minimum degree at least (1/2 + o(1))n contains every n-vertex tree with maximum degree . Krivelevich, Kwan, and Sudakov proved that for every n-vertex graph Gα with minimum degree at least αn for any fixed α > 0 and every n-vertex tree T with bounded maximum degree, one can still find a copy of T in Gα with high probability after adding O(n) randomly chosen edges to Gα. We extend the latter results to trees with (essentially) unbounded maximum degree; for a given and α > 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 αn in order to guarantee with high probability a copy of any fixed n-vertex tree with maximum degree at most Δ. | ||
| 650 | 4 | |a graph embedding | |
| 650 | 4 | |a Random graphs | |
| 650 | 4 | |a trees | |
| 700 | 1 | |a Kim, Jaehoon |e VerfasserIn |0 (DE-588)1262517826 |0 (DE-627)1810217857 |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |t Random structures & algorithms |d New York, NY [u.a.] : Wiley, 1990 |g 56(2020), 1, Seite 169-219 |h Online-Ressource |w (DE-627)306711141 |w (DE-600)1500812-5 |w (DE-576)082436185 |x 1098-2418 |7 nnas |a Spanning trees in randomly perturbed graphs |
| 773 | 1 | 8 | |g volume:56 |g year:2020 |g number:1 |g pages:169-219 |g extent:51 |a Spanning trees in randomly perturbed graphs |
| 856 | 4 | 0 | |u https://doi.org/10.1002/rsa.20886 |x Verlag |x Resolving-System |z lizenzpflichtig |3 Volltext |
| 856 | 4 | 0 | |u https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.20886 |x Verlag |z lizenzpflichtig |3 Volltext |
| 951 | |a AR | ||
| 992 | |a 20220715 | ||
| 993 | |a Article | ||
| 994 | |a 2020 | ||
| 998 | |g 1075006171 |a Joos, Felix |m 1075006171:Joos, Felix |d 700000 |d 728500 |e 700000PJ1075006171 |e 728500PJ1075006171 |k 0/700000/ |k 1/700000/728500/ |p 2 |y j | ||
| 999 | |a KXP-PPN181059734X |e 416679678X | ||
| BIB | |a Y | ||
| SER | |a journal | ||
| JSO | |a {"id":{"doi":["10.1002/rsa.20886"],"eki":["181059734X"]},"origin":[{"dateIssuedDisp":"2020","dateIssuedKey":"2020"}],"name":{"displayForm":["Felix Joos, Jaehoon Kim"]},"relHost":[{"physDesc":[{"extent":"Online-Ressource"}],"origin":[{"publisherPlace":"New York, NY [u.a.]","publisher":"Wiley","dateIssuedKey":"1990","dateIssuedDisp":"1990-"}],"id":{"zdb":["1500812-5"],"doi":["10.1002/(ISSN)1098-2418"],"eki":["306711141"],"issn":["1098-2418"]},"disp":"Spanning trees in randomly perturbed graphsRandom structures & algorithms","note":["Gesehen am 17.02.05"],"type":{"bibl":"periodical","media":"Online-Ressource"},"recId":"306711141","language":["eng"],"pubHistory":["1.1990 -"],"titleAlt":[{"title":"Random structures and algorithms"}],"part":{"text":"56(2020), 1, Seite 169-219","volume":"56","extent":"51","year":"2020","issue":"1","pages":"169-219"},"title":[{"title_sort":"Random structures & algorithms","title":"Random structures & algorithms"}]}],"physDesc":[{"extent":"51 S."}],"title":[{"title":"Spanning trees in randomly perturbed graphs","title_sort":"Spanning trees in randomly perturbed graphs"}],"person":[{"display":"Joos, Felix","roleDisplay":"VerfasserIn","role":"aut","family":"Joos","given":"Felix"},{"given":"Jaehoon","family":"Kim","role":"aut","display":"Kim, Jaehoon","roleDisplay":"VerfasserIn"}],"language":["eng"],"recId":"181059734X","type":{"media":"Online-Ressource","bibl":"article-journal"},"note":["Published on: 17 October 2019","Gesehen am 15.07.2022"]} | ||
| SRT | |a JOOSFELIXKSPANNINGTR2020 | ||