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 $\mathrm{\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)\le \mathrm{\Delta }+3$, and moreover $\chi (G^2)=\mathrm{\Delta }+1$ if $\mathrm{\Delta }\ge 6$; (2) $\lambda (G)\le \mathrm{\Delta }+7$, and moreover $\lambda (G)\le \mathrm{\Delta }+2$ if $\mathrm{\Delta }\ge 9$.