On the Number of Hamilton Cycles in Pseudo-Random Graphs
On the Number of Hamilton Cycles in Pseudo-Random Graphs
复制标题
关于伪随机图中的哈密顿循环数
DOI：
10.37236/1177
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Michael Krivelevich
中科院分区：
文献类型：
--
作者：
Michael Krivelevich
我们证明，如果$G$是一个$（n，d，\lambda）$-图（n$个顶点上的d$-正则图，其所有的非平凡特征值至多为$\lambda）$且满足以下条件：$\frac{d}{\lambda}\ge（\log n）^{1+\lambda}$对于某个常数$\lambda>0$;$\log d\cdot \log\frac{d}{\lambda}\gg \log n$，则$G$中的汉密尔顿圈数为$n！\左（\frac{d}{n}\right）^n（1+o（1））^n$.
We prove that if $G$ is an $(n,d,\lambda)$-graph (a $d$-regular graph on $n$ vertices, all of whose non-trivial eigenvalues are at most $\lambda)$ and the following conditions are satisfied: $\frac{d}{\lambda}\ge (\log n)^{1+\epsilon}$ for some constant $\epsilon>0$; $\log d\cdot \log\frac{d}{\lambda}\gg \log n$, then the number of Hamilton cycles in $G$ is $n!\left(\frac{d}{n}\right)^n(1+o(1))^n$.
随机图的近似哈密尔顿分解
影响因子：
1
作者：
Knox F
通讯作者：
Knox F