论文标题
几乎2型随机图
Almost-2-regular random graphs
论文作者
论文摘要
我们研究了配置模型的特殊情况，其中图表的几乎所有顶点都有$ 2 $。我们表明该图具有非常特殊且有趣的行为，特别是当图形由绝大多数的顶点$ 2 $组成，并且更高程度的顶点消失了，巨型组件包含$ n（1-o（1））$顶点，但是第二个成分仍然可以在$ n $ n $中生长。另一方面，当几乎所有的顶点都有$ 2 $的$ o（n）$，$ 1 $，没有线性尺寸的组成部分。
We study a special case of the configuration model, in which almost all the vertices of the graph have degree $2$. We show that the graph has a very peculiar and interesting behaviour, in particular when the graph is made up by a vast majority of vertices of degree $2$ and a vanishing proportion of vertices of higher degree, the giant component contains $n(1-o(1))$ vertices, but the second component can still grow polynomially in $n$. On the other hand, when almost all the vertices have degree $2$ except for $o(n)$ which have degree $1$, there is no component of linear size.
