Labeling outerplanar graphs with maximum degree three

An L(2,1)L(2,1)-labeling of a graph GG is an assignment of a non-negative integer to each vertex of GG 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 λλ-number of GG, denoted by λ(G)λ(G), is the minimum span over all L(2,1)L(2,1)-labelings of GG. Bodlaender et al. conjectured that if GG is an outerplanar graph of maximum degree ΔΔ, then λ(G)≤Δ+2λ(G)≤Δ+2. Calamoneri and Petreschi proved that this conjecture is true when Δ≥8Δ≥8 but false when Δ=3Δ=3. Meanwhile, they proved that λ(G)≤Δ+5λ(G)≤Δ+5 for any outerplanar graph GG with Δ=3Δ=3 and asked whether or not this bound is sharp. In this paper we answer this question by proving that λ(G)≤Δ+3λ(G)≤Δ+3 for every outerplanar graph with maximum degree Δ=3Δ=3. We also show that this bound Δ+3Δ+3 can be achieved by infinitely many outerplanar graphs with Δ=3Δ=3.