The L(2, 1)-F-labeling problem of graphs

In order to unify various concepts of distance-two labelings, we consider a general setting of distance-two labelings as follows. Given a graph H, an L(2, 1)-H-labeling of a graph G is a mapping f from V (G) to V (H) such that d_H(f(u), f(v)) ≥ 2 if d_G (u, v) = 1 and d_H (f(u), f(v)) ≥ 1 if d_G (u, v) = 2. Suppose F is a family of graphs. The L(2, 1)-F-labeling problem is to determine the L(2, 1)-F-labeling number λ_F (G) of a graph G which is the smallest number |E(H)| such that G has an L(2,1)-H-labeling for some H ∈ F. Notice that the L(2,1)-F-labeling is the L(2,1)-labeling (respectively, the circular distance-two labeling) if F is the family of all paths (respectively, cycles). The purpose of this paper is to study the L(2,1)-Flabeling problem.