| Decycling Number of Type-$k$ Halin Graphs |
| Received:April 10, 2024 Revised:October 11, 2024 |
| Key Words:
decycling number Halin graphs type-$k$ Halin graphs
|
| Fund Project:Supported by the National Natural Science Foundation of China (Grant Nos.11171114; 11401576) and Hotan Prefecture Science and Technology Bureau General Project (Grant No.20220212). |
| Author Name | Affiliation | | Wanjia ZHANG | School of Mathematics and Physics, Xinjiang Hetian College, Xinjiang 848000, P. R. China | | Chao YANG | School of Mathematics, Physics and Statistics, Shanghai University of Engineering Science, Shanghai 201620, P. R. China | | Han REN | School of Mathematical Sciences, East China Normal University, Shanghai 200241, P. R. China |
|
| Hits: 116 |
| Download times: 97 |
| 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. |
| Citation: |
| DOI:10.3770/j.issn:2095-2651.2025.02.001 |
| View Full Text View/Add Comment |
|
|
|
