Long paths and cycles in random subgraphs of graphs with large minimum degree

DOI10.1002/rsa.20508zbMath1314.05190arXiv1410.1438OpenAlexW2002045419MaRDI QIDQ4982618

Choongbum Lee, Michael Krivelevich, Benjamin Sudakov

Publication date: 9 April 2015

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1410.1438

zbMATH Keywords

Hamiltonicityrandom subgraphslong paths

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38) Distance in graphs (05C12) Vertex degrees (05C07)

Related Items (11)

Large complete minors in random subgraphs ⋮ Crux and Long Cycles in Graphs ⋮ Perfect matchings in random subgraphs of regular bipartite graphs ⋮ Long paths and cycles in random subgraphs of \(\mathcal{H}\)-free graphs ⋮ Long paths in heterogeneous random subgraphs of graphs with large minimum degree ⋮ The Threshold Probability for Long Cycles ⋮ On Hamilton cycles in Erdős‐Rényi subgraphs of large graphs ⋮ On randomk-out subgraphs of large graphs ⋮ Paths and cycles in random subgraphs of graphs with large minimum degree ⋮ Acquaintance Time of Random Graphs Near Connectivity Threshold ⋮ Long cycles in random subgraphs of graphs with large minimum degree

Cites Work

• Unnamed Item
• Unnamed Item
• Hamiltonian cycles in Dirac graphs
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Expanding graphs contain all small trees
• On large matchings and cycles in sparse random graphs
• The longest path in a random graph
• Relative lengths of paths and cycles in k-connected graphs
• Hamiltonian circuits in random graphs
• On the number of Hamiltonian cycles in Dirac graphs
• Homomorphiesätze für Graphen
• The phase transition in random graphs: A simple proof
• Long cycles in subgraphs of (pseudo)random directed graphs
• Local resilience of graphs
• Robust Hamiltonicity of Dirac graphs
• Random Graphs
• Some Theorems on Abstract Graphs

This page was built for publication: Long paths and cycles in random subgraphs of graphs with large minimum degree