Local resilience of almost spanning trees in random graphs
From MaRDI portal
Publication:3068763
DOI10.1002/rsa.20345zbMath1215.05154OpenAlexW1976052016MaRDI QIDQ3068763
József Balogh, Wojciech Samotij, Béla Csaba
Publication date: 17 January 2011
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.20345
Related Items (34)
Corrádi and Hajnal's Theorem for Sparse Random Graphs ⋮ Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs ⋮ Dirac-type theorems in random hypergraphs ⋮ Spanning trees of dense directed graphs ⋮ Dirac's theorem for random graphs ⋮ Long cycles in subgraphs of (pseudo)random directed graphs ⋮ Pancyclic subgraphs of random graphs ⋮ Almost-spanning universality in random graphs (extended abstract) ⋮ Local resilience of spanning subgraphs in sparse random graphs ⋮ Generating random graphs in biased Maker-Breaker games ⋮ Robust Hamiltonicity of random directed graphs ⋮ Rolling backwards can move you forward: On embedding problems in sparse expanders ⋮ Triangle resilience of the square of a Hamilton cycle in random graphs ⋮ On resilience of connectivity in the evolution of random graphs ⋮ Graph Tilings in Incompatibility Systems ⋮ Covering cycles in sparse graphs ⋮ Ramsey goodness of trees in random graphs ⋮ A Dirac-type theorem for Berge cycles in random hypergraphs ⋮ Independent Sets in Hypergraphs and Ramsey Properties of Graphs and the Integers ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ A Dirac-type theorem for Hamilton Berge cycles in random hypergraphs ⋮ Expanders Are Universal for the Class of All Spanning Trees ⋮ Robust Hamiltonicity of Dirac graphs ⋮ Almost‐spanning universality in random graphs ⋮ Universality of random graphs and rainbow embedding ⋮ Bandwidth theorem for random graphs ⋮ Optimal threshold for a random graph to be 2-universal ⋮ Almost spanning subgraphs of random graphs after adversarial edge removal ⋮ Hamiltonicity in random directed graphs is born resilient ⋮ Dirac’s theorem for random regular graphs ⋮ Hamiltonicity in random graphs is born resilient ⋮ Unnamed Item ⋮ The multicolor size-Ramsey numbers of cycles ⋮ Sharp threshold for the appearance of certain spanning trees in random graphs
Cites Work
- On two Hamilton cycle problems in random graphs
- Embedding nearly-spanning bounded degree trees
- On the resilience of long cycles in random graphs
- An algorithmic Friedman-Pippenger theorem on tree embeddings and applications
- Expanding graphs contain all small trees
- Hamiltonian circuits in random graphs
- Large bounded degree trees in expanding graphs
- Almost spanning subgraphs of random graphs after adversarial edge removal
- Resilient Pancyclicity of Random and Pseudorandom Graphs
- Szemerédi’s Regularity Lemma for Sparse Graphs
- Some Theorems on Abstract Graphs
This page was built for publication: Local resilience of almost spanning trees in random graphs
