Labeling cacti with a condition at distance two

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)| ≥ 2 if d(x, y) = 1 and | f (x) - f (y)| ≥ 1 if d(x, y) = 2. The L(2,1)-labeling number λ(G) of G is the smallest number k such that G has an L(2,1)-labeling with max{f (v) : v Î V(G)} = k. In this paper we present a graph family which has λ-number Δ+1 or Δ+2.