Article ID Journal Published Year Pages File Type
419125 Discrete Applied Mathematics 2007 12 Pages PDF
Abstract

For a given graph G of order n, a k  -L(2,1)L(2,1)-labelling is defined as a function f:V(G)→{0,1,2,…,k}f:V(G)→{0,1,2,…,k} such that |f(u)-f(v)|⩾2|f(u)-f(v)|⩾2 when dG(u,v)=1dG(u,v)=1 and |f(u)-f(v)|⩾1|f(u)-f(v)|⩾1 when dG(u,v)=2dG(u,v)=2. The L(2,1)L(2,1)-labelling number of G  , denoted by λ(G)λ(G), is the smallest number k such that G has a k  -L(2,1)L(2,1)-labelling. The consecutive L(2,1)L(2,1)-labelling is a variation of L(2,1)L(2,1)-labelling under the condition that the labelling f   is an onto function. The consecutive L(2,1)L(2,1)-labelling number of G   is denoted by λ¯(G). Obviously, λ(G)⩽λ¯(G)⩽|V(G)|-1 if G   admits a consecutive L(2,1)L(2,1)-labelling. In this paper, we investigate the graphs with λ¯(G)=|V(G)|-1 and the graphs with λ¯(G)=λ(G), in terms of their sizes, diameters and the number of components.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,