<i>L</i>(2, 1)-Labeling Halin Graphs with Maximum Degree Eight

Abstract

Suppose that T is a plane tree without vertices of degree 2 and with at least one vertex of at least degree 3, and C is the cycle obtained by connecting the leaves of T in a cyclic order. Set G=T∪C, which is called a Halin graph. A k-L(2,1)-labeling of a graph G=(V,E) is a mapping f:V(G)→{0,1,…,k} such that, for any x1,x2∈V(G), it holds that |f(x1)−f(x2)|≥2 if x1x2∈E(G), and |f(x1)−f(x2)|≥1 if the distance between x1 and x2 is 2 in G. The L(2,1)-labeling number, denoted λ(G), of G is the least k for which G is k-L(2,1)-labelable. In this paper, we prove that every Halin graph G with Δ=8 has λ(G)≤10. This improves a known result, which states that every Halin graph G with Δ≥9 satisfies λ(G)≤Δ+2. This result, together with some known results, shows that every Halin graph G satisfies λ(G)≤Δ+6.

Keywords

• Halin graph
• <i>L</i>(2, 1)-labeling
• maximum degree