$L(2,1)$-labeling of Block Graphs

Abstract

An $L(2,1)$-labeling of a graph $G=(V,E)$ is a function $f$ from its vertex set $V$ to the set of nonnegative integers such that $|f(x)–f(y)|\ge 2$ if $xy\in E$ and $|f(x)–f(y)|\ge 1$ if $x$ and $y$ are at distance two apart. The span of an $L(2,1)$-labeling $f$ is the maximum value of $f(x)$ over all $x\in V$. The \emph{$L(2,1)$-labeling number} of $G$, denoted $\lambda (G)$, is the least integer $k$ such that $G$ has an $L(2,1)$-labeling of span $k$. Chang and Kuo [1996, SIAM J. Discrete
Mathematics, Vol 9, No. 2, pp. $309—316]$ proved that $\lambda (G)\le 2\mathrm{\Delta }(G)$ and conjectured that $\lambda (G)\le \mathrm{\Delta }(G)+\omega (G)$ for a strongly chordal graph $G$, where $\mathrm{\Delta }(G)$ and $\omega (G)$ are the maximum degree and maximum clique size of $G$, respectively. In this paper, we propose an algorithm for $L(2,1)$-labeling a block graph $G$ with $\mathrm{\Delta }(G)+\omega (G)+1$ colors. As block graphs are strongly chordal graphs, our result proves Chang and Kuo’s conjecture for block graphs. We also obtain better bounds of $\lambda (G)$ for some special subclasses of block graphs. Finally, we investigate finding the exact value of $\lambda (G)$ for a block graph $G$.