Decycling number of type-k Halin graphs

Abstract:

      A set $S$ of vertices of a graph $G$ is called a decycling set if $G-S$ is acyclic. The smallest size of a decycling set is called the decycling number of $G$ and is denoted by $\nabla(G)$. In this paper, we investigate the decycling number of type-$k$ Halin graphs, focusing on those that are formed from trees that have just two degrees $k$ and $3$. For any type-$k$ Halin graph $G$ of order $n$, we prove that \[\frac{(k-2)n+k^{2}-4k+5}{(k-1)^{2}}\leq \nabla(G)\leq \frac{n+k-3}{k-1}.\] The result not only supports the largest forest conjecture due to Albertson and Berman (1976), but also offers a tight lower bound for the decycling number of type-$3$ Halin graphs and several type-$k$ Halin graphs. Moreover, a new formula to determine the cardinality of any decycling set $S$ of a type-$k$ Halin graph $G$ is provided.