Hamiltonicity of random graphs in the stochastic block model

DOI10.1137/19M1296069MaRDI QIDQ5009335zbMATH OpenOpenAlexFDO

Authors Michael Anastos, Pu Gao, Alan Frieze

Publication date 20 August 2021

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

block modelHamilton cyclesrandom graphs

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We study the Hamiltonicity of the following model of a random graph. Suppose that we partition [n] into V_1,V_2,...,V_k and add edge {x,y} to our graph with probability p if there exists i such that x,yin 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.

Recommendations

• Random graph's Hamiltonicity is strongly tied to its minimum degree
• On two Hamilton cycle problems in random graphs
• Sharp thresholds for Hamiltonicity in random intersection graphs
• Hamilton cycles in random geometric graphs
• scientific article; zbMATH DE number 3922707

Cites work

• Community detection and stochastic block models: recent developments
• Introduction to Random Graphs
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Limit distribution for the existence of Hamiltonian cycles in random bipartite graphs

Cited in

(4)

• Hamiltonicity in random graphs is born resilient
• scientific article; zbMATH DE number 4031730 (Why is no real title available?)
• Characterization of expansion-related properties of modular graphs
• Embedding theorems for random graphs with specified degrees

This page was built for publication: Hamiltonicity of random graphs in the stochastic block model

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