论文标题
在$ 4 $期权随机图的de废数量上
On the Decycling Number of $4$-regular Random Graphs
论文作者
论文摘要
图$ g $的Decycling数字$ ϕ（g）$是可以从$ G $中删除的最小顶点，因此所得的图没有周期。 Bau，Wormald和Zhou猜想，概率趋向于$ n $ Vertices上的随机$ 4 $ gragher Graph $ g_4（n）$的脱水数量等于$ \ lceil（n+1）/3 \ rceil $。在本文中，我们表明该猜想是渐近地持有的，即几乎肯定是$ \ lim_ {n \ to \ infty} ϕ（g_4（n））/n = 1/3 $。
The decycling number $ϕ(G)$ of a graph $G$ is the smallest number of vertices which can be removed from $G$ so that the resulting graph has no cycles. Bau, Wormald and Zhou conjectured that with probability tending to one the decycling number of the random $4$-regular graph $G_4(n)$ on $n$ vertices is equal to $\lceil (n+1)/3\rceil$. In this paper we show that this conjecture holds asymptotically, i.e. asymptotically almost surely $\lim_{n \to \infty}ϕ(G_4(n))/n = 1/3$.
