Hamiltonicity of Random Graphs in the Stochastic Block Model
Hamiltonicity of Random Graphs in the Stochastic Block Model
复制标题
DOI：
10.1137/19m1296069
复制
发表时间：
2019-10
期刊：
影响因子：
--
通讯作者：
Michael Anastos;A. Frieze;Pu Gao
中科院分区：
文献类型：
--
作者：
Michael Anastos;A. Frieze;Pu Gao
我们研究了随机图的以下模型的汉密尔顿性。假设我们将[n]分配到v_1，v_2，...，v_k，然后将edge {x，y}添加到我们的图形中，如果存在i，则概率p如果存在i，则x，y \ in v_i in v_i。否则，我们将带有概率q的边缘添加。我们用G（N，P，Q）表示该模型，并在各种条件下为Hamiltonicity（包括关键的窗口分析）提供了严格的结果。
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,y\in 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.