A New Characterization of Disk Graphs and its Application

Abstract

An $L(2,1)$-labeling of a graph $G$ is a function $f$ from the vertex set $V(G)$ to the set of all nonnegative integers such that $|f(x)–f(y)|\ge 2$ if $d(x,y)=1$ and $|f(x)–f(y)|\ge 1$ if $d(x,y)=2$, where $d(x,y)$ denotes the distance between $x$ and $y$ in $G$. The $L(2,1)$-labeling number, $\lambda (G)$, of $G$ is the smallest number $k$ such that $G$ has an $L(2,1)$-labeling $f$ with $max\{f(v):v\in V(G)\}=k$. In this paper, we present a new characterization on $d$-disk graphs for $d>1$. As an application, we give upper bounds on the $L(2,1)$-labeling number for these classes of graphs.