Distance Two Labeling of Halin Graphs

Abstract

Let \(T\) be a tree with no vertices of degree \(2\) and at least one vertex of degree \(3\) or more. A Halin graph \(G\) is a plane graph obtained by connecting the leaves of \(T\) in the cyclic order determined by the planar drawing of \(T\). Let \(\Delta\), \(\lambda(G)\), and \(\chi(G^2)\) denote, respectively, the maximum degree, the \(L(2,1)\)-labeling number, and the chromatic number of the square of \(G\). In this paper, we prove the following results for any Halin graph \(G\): (1) \(\chi(G^2) \leq \Delta + 3\), and moreover \(\chi(G^2) = \Delta + 1\) if \(\Delta \geq 6\); (2) \(\lambda(G) \leq \Delta + 7\), and moreover \(\lambda(G) \leq \Delta + 2\) if \(\Delta \geq 9\).