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)| \geq 2\) if \(d(x, y) = 1\) and \(|f(x) – f(y)| \geq 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.