The \(L(2,1)\)-Labeling Problem on Ditrees

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\quad\text{if}\quad d_G(x,y)=1\) and \(|f(x)-f(y)|\geq 1\quad\text{if}\quad d_G(x,y)=2\). The \(L(2,1)\)-labeling problem is to find the smallest number \(\lambda(G)\) such that there exists an \(L(2,1)\)-labeling function with no label greater than \(\lambda(G)\). Motivated by the channel assignment problem introduced by Hale, the \(L(2,1)\)-labeling problem has been extensively studied in the past decade. In this paper, we study this concept for digraphs. In particular, results on ditrees are given.