An extremal problem on non-full colorable graphs

For a given graph G of order n, a k-L (2, 1)-labelling is defined as a function f : V (G) → { 0, 1, 2, ... k } such that | f (u) - f (v) | ≥ 2 when d_G (u, v) = 1 and | f (u) - f (v) | ≥ 1 when d_G (u, v) = 2. The L (2, 1)-labelling number of G, denoted by λ (G), is the smallest number k such that G has a k-L (2, 1)-labelling. The hole index ρ (G) of G is the minimum number of integers not used in a λ (G)-L (2, 1)-labelling of G. We say G is full-colorable if ρ (G) = 0; otherwise, it will be called non-full colorable. In this paper, we consider the graphs with λ (G) = 2 m and ρ (G) = m, where m is a positive integer. Our main work generalized a result by Fishburn and Roberts [No-hole L (2, 1)-colorings, Discrete Appl. Math. 130 (2003) 513-519].