Hamilton cycles in 3‐out
Hamilton cycles in 3‐out
复制标题
汉密尔顿循环三出
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
A. Frieze
中科院分区：
文献类型：
--
作者：
T. Bohman;A. Frieze
设G3-out表示顶点集[n]上的随机图，其中每个顶点随机均匀地选择三个邻居。请注意，G3‐out的最小度为3，平均度为6。我们证明了当n趋于无穷大时，G3-out是哈密顿量的概率变为1。© 2009 Wiley Periodicals，Inc.随机结构算法，2009
Let G3‐out denote the random graph on vertex set [n] in which each vertex chooses three neighbors uniformly at random. Note that G3‐out has minimum degree 3 and average degree 6. We prove that the probability that G3‐out is Hamiltonian goes to 1 as n tends to infinity. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009