Decycling Number of Type-k Halin Graphs  

作　　者：Wanjia ZHANG Chao YANG Han REN 

机构地区：[1]School of Mathematics and Physics,Xinjiang Hetian College,Xinjiang 848000,P.R.China [2]School of Mathematics,Physics and Statistics,Shanghai University of Engineering Science,Shanghai 201620,P.R.China [3]School of Mathematical Sciences,East China Normal University,Shanghai 200241,P.R.China

出　　处：《Journal of Mathematical Research with Applications》2025年第2期143-151,共9页数学研究及应用(英文版)

基　　金：Supported by the National Natural Science Foundation of China(Grant Nos.11171114,11401576);Hotan Prefecture Science and Technology Bureau General Project(Grant No.20220212)。

摘　　要：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 ∇(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(k-2)n+k^(2)-4k+5/(k-1)^(2)≤∇(G)≤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.

关 键 词：decycling number Halin graphs type-k Halin graphs 

分 类 号：O157.5[理学—数学]