Hamiltonicity of random graphs in the stochastic block model

2019/10/28 by Michael Anastos, Alan Frieze, Anastos, Michael +3 · 1 citation
Mathematics · #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1910.12594

openalex publication_date 2019/10/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the Hamiltonicity of the following model of a random graph. Suppose that we partition [n] into V₁,V₂,...,V_k and add edge x,y to our graph with probability p if there exists i such that x,y∈ V_i. Otherwise, we add the edge with probbability q. We denote this model by G(n, p,q) and give tight results for Hamiltonicity, including a critical window analysis, under various conditions.

Citations

• Hamilton Cycles in Random Graphs: a bibliography

Cited by

• The Chromatic Number of Dense Random Block Graphs

Related

• Hamilton cycles in a semi-random graph model
• Hamiltonicity of random subgraphs of the hypercube
• Random graph's Hamiltonicity is strongly tied to its minimum degree
• Hamiltonicity of the random geometric graph
• Hamiltonicity in random graphs is born resilient