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 n...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.展开更多
Let G be a simple connected graph with vertex set V(G)and edge set E(G).Then the Sombor index of graph G is defined as SO(G)=Σ_(uv∈E(G))√d^(2)(u)+d^(2)(v),where d(u)denotes the degree of vertex u.In this paper,the ...Let G be a simple connected graph with vertex set V(G)and edge set E(G).Then the Sombor index of graph G is defined as SO(G)=Σ_(uv∈E(G))√d^(2)(u)+d^(2)(v),where d(u)denotes the degree of vertex u.In this paper,the maximum and minimum values of the Sombor index for Halin graphs are obtained,and the corresponding extremal graphs are characterized.展开更多
基金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.
基金supported by the National Natural Science Foundation of China(No.12201634)the Hunan Provincial Natural Science Foundation of China(Nos.2020JJ4423,2023JJ30070)。
文摘Let G be a simple connected graph with vertex set V(G)and edge set E(G).Then the Sombor index of graph G is defined as SO(G)=Σ_(uv∈E(G))√d^(2)(u)+d^(2)(v),where d(u)denotes the degree of vertex u.In this paper,the maximum and minimum values of the Sombor index for Halin graphs are obtained,and the corresponding extremal graphs are characterized.
