On the Decycling Number of $4$-regular Random Graphs

Abstract

The decycling number $\varphi (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 }\varphi (G_4(n))/n=1/3$.

There is an error in Observation 3.3 in the paper, leading to false conclusions later on