\input zb-basic
\input zb-ioport
\iteman{io-port 06109944}
\itemau{Li, Xiangwen; Zhou, Sanming}
\itemti{Labeling outerplanar graphs with maximum degree three.}
\itemso{Discrete Appl. Math. 161, No. 1-2, 200-211 (2013).}
\itemab
Summary: An $L(2,1)$-labeling of a graph $G$ is an assignment of a non-negative integer to each vertex of $G$ such that adjacent vertices receive integers that differ by at least two and vertices at distance two receive distinct integers. The span of such a labeling is the difference between the largest and smallest integers used. The $\lambda $-number of $G$, denoted by $\lambda (G)$, is the minimum span over all $L(2,1)$-labelings of $G$. Bodlaender et al. conjectured that if $G$ is an outerplanar graph of maximum degree $\Delta $, then $\lambda (G)\le \Delta +2$. Calamoneri and Petreschi proved that this conjecture is true when $\Delta \ge 8$ but false when $\Delta =3$. Meanwhile, they proved that $\lambda (G)\le \Delta +5$ for any outerplanar graph G with $\Delta =3$ and asked whether or not this bound is sharp. In this paper we answer this question by proving that $\lambda (G)\le \Delta +3$ for every outerplanar graph with maximum degree $\Delta =3$. We also show that this bound $\Delta +3$ can be achieved by infinitely many outerplanar graphs with $\Delta =3$.
\itemrv{~}
\itemcc{}
\itemut{$L(2; 1)$-labeling; outerplanar graphs; $\lambda $-number}
\itemli{doi:10.1016/j.dam.2012.08.018}
\end