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.展开更多
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.展开更多
Let G=(V,E,F)be a connected loopless plane graph,with vertex set V,edge set E,and face set F.For any adjacent faces e_(1) and e_(2),if they are incident to the same face and appear consecutively on the edge of that fa...Let G=(V,E,F)be a connected loopless plane graph,with vertex set V,edge set E,and face set F.For any adjacent faces e_(1) and e_(2),if they are incident to the same face and appear consecutively on the edge of that face,then it is said that e1 and e_(2) are facially adjacent.A plane graph G is called weakly edge-face k-colorable indicating that there is a mappingπ:E∪F→{1,2,…,k}such that any two incident edges and faces,adjacent faces,and facially adjacent edges receive distinct colors.The weakly edge-face chromatic number of G,denoted by-χ_(ef)(G),is defined to be the smallest integer k such that G has a weakly edge-face k-coloring.In 2016,Fabrici conjectured that every connected,loopless,and bridgeless plane graph was weakly edge-face 5-colorable.In this paper,a sufficient condition is provided for the foregoing conjecture to prove that Halin graphs are weakly edge-face 5-colorable in which the upper bound 5 is the best possible.展开更多
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.展开更多
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.展开更多
For a graph G and two positive integers j and k an m-L j k -edge-labeling of G is an assignment from the set 0 1 … m-to the edges such that adjacent edges receive labels that differ by at least j and edges at distanc...For a graph G and two positive integers j and k an m-L j k -edge-labeling of G is an assignment from the set 0 1 … m-to the edges such that adjacent edges receive labels that differ by at least j and edges at distance two receive labels that differ by at least k.Theλ′j k-number of G denoted byλ′j k G is the minimum integer m overall m-L j k -edge-labeling of G.The necklace is a specific type of Halin graph.The L 1 2 -edge-labeling of necklaces is studied and the lower and upper bounds on λ′1 2-number for necklaces are given.Also both the lower and upper bounds are attainable.展开更多
The strong embedding conjecture states that any 2-connected graph has a strong embedding on some surface. It implies the circuit double cover conjecture: Any 2-connected graph has a circuit double cover. Conversely, i...The strong embedding conjecture states that any 2-connected graph has a strong embedding on some surface. It implies the circuit double cover conjecture: Any 2-connected graph has a circuit double cover. Conversely, it is not true. But for a 3-regular graph, the two conjectures are equivalent. In this paper, a characterization of graphs having a strong embedding with exactly 3 faces, which is the strong embedding of maximum genus, is given. In addition, some graphs with the property are provided. More generally, an upper bound of the maximum genus of strong embeddings of a graph is presented too. Lastly, it is shown that the interpolation theorem is true to planar Halin graph.展开更多
基金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 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.
文摘Let G=(V,E,F)be a connected loopless plane graph,with vertex set V,edge set E,and face set F.For any adjacent faces e_(1) and e_(2),if they are incident to the same face and appear consecutively on the edge of that face,then it is said that e1 and e_(2) are facially adjacent.A plane graph G is called weakly edge-face k-colorable indicating that there is a mappingπ:E∪F→{1,2,…,k}such that any two incident edges and faces,adjacent faces,and facially adjacent edges receive distinct colors.The weakly edge-face chromatic number of G,denoted by-χ_(ef)(G),is defined to be the smallest integer k such that G has a weakly edge-face k-coloring.In 2016,Fabrici conjectured that every connected,loopless,and bridgeless plane graph was weakly edge-face 5-colorable.In this paper,a sufficient condition is provided for the foregoing conjecture to prove that Halin graphs are weakly edge-face 5-colorable in which the upper bound 5 is the best possible.
基金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.
基金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.
基金The National Natural Science Foundation of China(No.10971025,10901035)
文摘For a graph G and two positive integers j and k an m-L j k -edge-labeling of G is an assignment from the set 0 1 … m-to the edges such that adjacent edges receive labels that differ by at least j and edges at distance two receive labels that differ by at least k.Theλ′j k-number of G denoted byλ′j k G is the minimum integer m overall m-L j k -edge-labeling of G.The necklace is a specific type of Halin graph.The L 1 2 -edge-labeling of necklaces is studied and the lower and upper bounds on λ′1 2-number for necklaces are given.Also both the lower and upper bounds are attainable.
基金the National Natural Sciences Foundation of China (No.10271048).
文摘The strong embedding conjecture states that any 2-connected graph has a strong embedding on some surface. It implies the circuit double cover conjecture: Any 2-connected graph has a circuit double cover. Conversely, it is not true. But for a 3-regular graph, the two conjectures are equivalent. In this paper, a characterization of graphs having a strong embedding with exactly 3 faces, which is the strong embedding of maximum genus, is given. In addition, some graphs with the property are provided. More generally, an upper bound of the maximum genus of strong embeddings of a graph is presented too. Lastly, it is shown that the interpolation theorem is true to planar Halin graph.
