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

DOI10.1002/rsa.20508zbMath1314.05190arXiv1410.1438MaRDI 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

Hamiltonicity; random subgraphs; long paths

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

05C80: Random graphs (graph-theoretic aspects)

05C38: Paths and cycles

05C12: Distance in graphs

05C07: Vertex degrees

Related Items

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

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