Circular Distance Two Labeling and the $\lambda$-Number for Outerplanar Graphs
Daphne Der‐Fen Liu, Xuding Zhu · SIAM Journal on Discrete Mathematics · 2005
Let G be a graph. A circular distance two labeling with span k is a function $f: V(G) \to \{0, 1, 2, \ldots, k-1\}$ such that (1) $2 \leq |f(u)-f(v)| \leq k-2$ if u and v are adjacent and (2) $f(u) eq f(v)$ if u and v are of distance two apart. We denote by $\lambda_c(G)$ the smallest span of a circular distance two labeling for G. Let $\Delta(G)$ be the maximum degree of G. We prove, for any outerplanar graph G with $\Delta(G) \geq 15$, $\lambda_c(G)=\Delta(G) +3$. It is also shown that there exist outerplanar graphs G with $\Delta(G) = 2, 3, 4, 5$ for which $\lambda_c(G) = \Delta(G) +4$. Moreover, we prove that $\lambda_c(G) \leq \Delta(G) +5$ for any triangulated outerplanar graph, $\lambda_c(G) \leq \Delta(G) +7$ for any outerplanar graph, and $\lambda_c(G) \leq \Delta(G) +4$ for any outerplanar graph with $\Delta(G) \geq 11$. Immediate consequences of our results include that $\lambda(G) \leq \Delta(G) + 2$ for any outerplanar graphs with $\Delta(G) \geq 15$, where $\lambda(G)$ is the minimum k of a k-L(2, 1)-labeling (or distance two labeling) for G.