Local resilience of spanning subgraphs in sparse random graphs

DOI10.1016/J.ENDM.2015.06.071MaRDI QIDQ322312zbMATH OpenOpenAlexFDO

Authors Peter Allen, Julia Böttcher, Julia Ehrenmüller, Anusch Taraz

Publication date 14 October 2016

Full work available at URL http://eprints.lse.ac.uk/64637/1/__lse.ac.uk_storage_LIBRARY_Secondary_libfile_shared_repository_Content_Allen%2C%20Peter_Local%20resilience_Allen_Local%20resilience_2015.pdf

zbMATH Keywords

extremal graph theoryrandom graphsresiliencesparse regularity

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Density (toughness, etc.) (05C42)

Recommendations

• Local resilience of almost spanning trees in random graphs
• The bandwidth theorem in sparse graphs
• A spanning bandwidth theorem in random graphs

Cites work

• Bandwidth theorem for random graphs
• Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
• Corrádi and Hajnal's theorem for sparse random graphs
• Dirac's theorem for random graphs
• Embedding large subgraphs into dense graphs
• Local resilience of almost spanning trees in random graphs
• On the resilience of long cycles in random graphs
• Proof of the bandwidth conjecture of Bollobás and Komlós
• Some Theorems on Abstract Graphs

Cited in

(6)

• Local resilience of an almost spanning k‐cycle in random graphs
• Local structure theorems for Erdős-Rényi graphs and their algorithmic applications
• The bandwidth theorem in sparse graphs
• On Komlós' tiling theorem in random graphs
• Local resilience of almost spanning trees in random graphs
• Local resilience of graphs

This page was built for publication: Local resilience of spanning subgraphs in sparse random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q322312)