Labelling Graphs with a Condition at Distance 2

Abstract

Given a simple graph $G = ( V,E )$ and a positive number d, an $L_d ( 2,1 )$-labelling of G is a function $f:V ( G ) \to [ 0,\infty )$ such that whenever $x,y \in V$ are adjacent, $| f ( x ) - f ( y ) | \geq 2d$, and whenever the distance between x and y is two, $| f ( x ) - f ( y ) | \geq d$. The $L_d ( 2,1 )$-labelling number$( G,d )$ is the smallest number m such that G has an $L_d ( 2,1 )$-labelling f with $\max \{ f ( v ): v \in V \} = m$. It is shown that to determine $\lambda ( G,d )$, it suffices to study the case when $d = 1$ and the labelling is nonnegative integral-valued. Let $\lambda ( G ) = \lambda ( G,1 )$. The labelling numbers of special classes of graphs, e.g., $\lambda ( C ) = 4$ for any cycle C, are described. It is shown that for graphs of maximum degree $\Delta ,\lambda ( G ) \leq \Delta ^2 + 2\Delta $. If G is diameter $2,\lambda ( G ) \leq \Delta ^2 $, a sharp bound for some $\Delta $. Determining $\lambda ( G )$ is shown to be NP-complete by relating it to the problem of finding Hamilton paths.