Verlagslink DOI: 10.1016/j.endm.2015.06.071
Titel: Local resilience of spanning subgraphs in sparse random graphs
Sprache: Englisch
Autor/Autorin: Allen, Peter 
Böttcher, Julia 
Ehrenmüller, Julia 
Taraz, Anusch 
Schlagwörter: Extremal graph theory; Random graphs; Resilience; Sparse regularity
Erscheinungs­datum: 12-Nov-2015
Verlag: Elsevier Science
Quellenangabe: Electronic Notes in Discrete Mathematics 49: 513-521 (2015-11)
Zusammenfassung (englisch): 
For each real γ>0 and integers δ≥2 and k≥1, we prove that there exist constants β>0 and C>0 such that for all p≥C(logn/n)1/δ the random graph G(n, p) asymptotically almost surely contains - even after an adversary deletes an arbitrary (1/k-γ)-fraction of the edges at every vertex - a copy of every n-vertex graph with maximum degree at most δ, bandwidth at most βn and at least Cmaxp-2, p-1logn vertices not in triangles.
URI: http://hdl.handle.net/11420/10812
ISSN: 1571-0653
Zeitschrift: Electronic notes in discrete mathematics 
Institut: Mathematik E-10 
Dokumenttyp: Artikel/Aufsatz
Enthalten in den Sammlungen:Publications without fulltext

Zur Langanzeige

Seitenansichten

39
Letzte Woche
0
Letzten Monat
checked on 01.10.2022

SCOPUSTM   
Zitate

1
Letzte Woche
0
Letzten Monat
checked on 30.06.2022

Google ScholarTM

Prüfe

Volltext ergänzen

Feedback zu diesem Datensatz

Diesen Datensatz zitieren

Export

Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.