$L(2,1)$-Labeling of Hamiltonian graphs with Maximum Degree 3
Jeong-Hyun Kang · SIAM Journal on Discrete Mathematics · 2008
An integer coloring f of the vertices of a graph G is an $L(2,1)$-labeling if $|f(u) - f(v)| \geq 2$ for each edge $uv$ and $|f(u) - f(v)| \geq 1$ for each pair $u,v \in V(G)$ at distance 2 apart. The $L(2,1)$-labeling span of G, denoted by $\lambda (G)$, is the smallest number t such that G has an $L(2,1)$-labeling using labels $\{0,1, \dots, t\}$. Griggs and Yeh [SIAM J. Discrete Math., 5 (1992), pp. 586–595] conjectured that always $\lambda(G) \leq (\Delta(G))^2$, where $\Delta(G)$ is the maximum degree of G and $\Delta(G) \geq 2$. In this paper, we will prove that the conjecture holds if G is a Hamiltonian graph with maximum degree 3.