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.展开更多
A vertex distinguishing edge coloring of a graph G is a proper edge coloring of G such that any pair of vertices has the distinct sets of colors. The minimum number of colors required for a vertex distinguishing edge ...A vertex distinguishing edge coloring of a graph G is a proper edge coloring of G such that any pair of vertices has the distinct sets of colors. The minimum number of colors required for a vertex distinguishing edge coloring of a graph C is denoted by Xs＇8（G）. In this paper, we obtained upper bounds on the vertex distinguishing chromatic index of 3-regular Halin graphs and Halin graphs with △（G） ≥ 4, respectively.展开更多
In this paper we show that the face-width of any embedding of a Halin graph（a type of planar graph） in the torus is one, and give a formula for determining the number of all nonequivalent embeddings of a Halin graph...In this paper we show that the face-width of any embedding of a Halin graph（a type of planar graph） in the torus is one, and give a formula for determining the number of all nonequivalent embeddings of a Halin graph in the torus.展开更多
Let G be a connected graph having a perfect matching.The graph G is said to be induced matching(IM)extendable if every induced matching M of G is contained in a perfect matching of G.In this paper,we show that Halin g...Let G be a connected graph having a perfect matching.The graph G is said to be induced matching(IM)extendable if every induced matching M of G is contained in a perfect matching of G.In this paper,we show that Halin graph G=T∪C is IM-extendable if and only if its characteristic tree T is isomorphic to K_(1,3),K_(1,5),K_(1,7) or S_(2,2).展开更多
The Q-index of a graph G is the largest eigenvalue q（G） of its signless Laplacian matrix Q（G）. In this paper, we prove that the wheel graph W_n = K_1 ∨C_（n-1）is the unique graph with maximal Q-index among all H...The Q-index of a graph G is the largest eigenvalue q（G） of its signless Laplacian matrix Q（G）. In this paper, we prove that the wheel graph W_n = K_1 ∨C_（n-1）is the unique graph with maximal Q-index among all Halin graphs of order n. Also we obtain the unique graph with second maximal Q-index among all Halin graphs of order n.展开更多
For any graph?G,?G?together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number?k(G)?of a graph?G?is defined to be the smallest number of such isolated ver...For any graph?G,?G?together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number?k(G)?of a graph?G?is defined to be the smallest number of such isolated vertices. In general, it is hard to compute the competition number?k(G)?for a graph?G?and chara-cterizing a graph by its competition number has been one of important research problems in the study of competition graphs. A 2-connected planar graph?G?with minimum degree at least 3 is a pseudo-Halin graph if deleting the edges on the boundary of a single face?f0?yields a tree. It is a Halin graph if the vertices of?f0?all have degree 3 in?G. In this paper, we compute the competition numbers of a kind of pseudo-Halin graphs.展开更多
A proper k-edge coloring f of graph G(V, E) is said to be a k:-adjacent strong edge coloring of graph G(V,E) iff every uv∈E(G) satisfy f[u]≠f/[v], where f[u] = {f(uw)|uw ∈E(G)} then f is called k-adjacent strong ed...A proper k-edge coloring f of graph G(V, E) is said to be a k:-adjacent strong edge coloring of graph G(V,E) iff every uv∈E(G) satisfy f[u]≠f/[v], where f[u] = {f(uw)|uw ∈E(G)} then f is called k-adjacent strong edge coloring of G, is abbreviated k-ASEC: and x'as(G) = min{k|k-ASEC of G} is called the adjacent strong edge chromatic number. In this paper, we study the x'as(G) of Halin graphs with △A(G)≥5.展开更多
Let G be a planar graph with δ(G)≥3, fo be a face of G. In this paper it is proved that for any Halin graph with △(G)≥6, X (G)＝△(G)+1, where △(G), Xo (G) denote the maximum degree and the complete chromatic num...Let G be a planar graph with δ(G)≥3, fo be a face of G. In this paper it is proved that for any Halin graph with △(G)≥6, X (G)＝△(G)+1, where △(G), Xo (G) denote the maximum degree and the complete chromatic number of G, respectively.展开更多
基金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.
基金Supported by the National Natural Science Foundation of China(10971198)the Zhejiang Natural Science Foundation of China(Z6110786)
文摘A vertex distinguishing edge coloring of a graph G is a proper edge coloring of G such that any pair of vertices has the distinct sets of colors. The minimum number of colors required for a vertex distinguishing edge coloring of a graph C is denoted by Xs＇8（G）. In this paper, we obtained upper bounds on the vertex distinguishing chromatic index of 3-regular Halin graphs and Halin graphs with △（G） ≥ 4, respectively.
基金Supported by the NNSF of China(10671073)Supported by the NSF of Jiangsu’s Universities( 07KJB110090)
文摘In this paper we show that the face-width of any embedding of a Halin graph（a type of planar graph） in the torus is one, and give a formula for determining the number of all nonequivalent embeddings of a Halin graph in the torus.
基金Supported by the National Natural Science Foundation of China(Grant Nos.61702291,11801371)Key Research Project in Universities of Henan Province(Grant No.21B110004)。
文摘Let G be a connected graph having a perfect matching.The graph G is said to be induced matching(IM)extendable if every induced matching M of G is contained in a perfect matching of G.In this paper,we show that Halin graph G=T∪C is IM-extendable if and only if its characteristic tree T is isomorphic to K_(1,3),K_(1,5),K_(1,7) or S_(2,2).
基金Supported by the National Natural Science Foundation of China(Grant No.11171273)the Seed Foundation of Innovation and Creation for Graduate Students in Northwestern Polytechnical University(Grant No.Z2016170)
文摘The Q-index of a graph G is the largest eigenvalue q（G） of its signless Laplacian matrix Q（G）. In this paper, we prove that the wheel graph W_n = K_1 ∨C_（n-1）is the unique graph with maximal Q-index among all Halin graphs of order n. Also we obtain the unique graph with second maximal Q-index among all Halin graphs of order n.
文摘For any graph?G,?G?together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number?k(G)?of a graph?G?is defined to be the smallest number of such isolated vertices. In general, it is hard to compute the competition number?k(G)?for a graph?G?and chara-cterizing a graph by its competition number has been one of important research problems in the study of competition graphs. A 2-connected planar graph?G?with minimum degree at least 3 is a pseudo-Halin graph if deleting the edges on the boundary of a single face?f0?yields a tree. It is a Halin graph if the vertices of?f0?all have degree 3 in?G. In this paper, we compute the competition numbers of a kind of pseudo-Halin graphs.
基金Supported by NNSFC(19871036)"Qing Lan"talent funds of Lanzhou Railway Institute.
文摘A proper k-edge coloring f of graph G(V, E) is said to be a k:-adjacent strong edge coloring of graph G(V,E) iff every uv∈E(G) satisfy f[u]≠f/[v], where f[u] = {f(uw)|uw ∈E(G)} then f is called k-adjacent strong edge coloring of G, is abbreviated k-ASEC: and x'as(G) = min{k|k-ASEC of G} is called the adjacent strong edge chromatic number. In this paper, we study the x'as(G) of Halin graphs with △A(G)≥5.
文摘Let G be a planar graph with δ(G)≥3, fo be a face of G. In this paper it is proved that for any Halin graph with △(G)≥6, X (G)＝△(G)+1, where △(G), Xo (G) denote the maximum degree and the complete chromatic number of G, respectively.
