Institution: | a Department of Mathematics, East China Normal University, Shanghai 200062, China b Institute of Theoretical Computing, ECNU, Shanghai 200062, China c Department of Mathematics, Chuzhou University, Anhui 239012, China |
Abstract: | 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 dG(u,v)=1 and |f(u)-f(v)|?1 when dG(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)=2m 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]. |